Feng Shi

Associate Professor

School of Computer Science and Engineering

Central South University

Changsha 410083, China


Email: fengshi [AT] csu [DOT] edu [DOT] cn

Office 428, Information Building, New Campus


Member of Institute of Computer Theory and Software

   Personal Profile

        Feng Shi is currently an associate professor in School of Computer Science and Engineering, Central South University.
     From Sep. 2011 to Dec. 2017, he obtained a Ph.D. degree in Computer Science and Technology at Central South University, under the supervision of Prof. Jianer Chen and Prof. Jianxin Wang.
From Oct. 2015 to Oct. 2017, he visited the group Optimisation and Logistics at the University of Adelaide in Australia, under the supervision of Prof. Frank Neumann.
From Sep. 2007 to Jul. 2011, he received his B.Eng degree in Computer Science and Technology at Central South University.

  Research Interests

Students who are interested in doing Master Degree in the following areas are welcome to contact me.
  • Graph Algorithms
  • Fixed-parameter Algorithms
  • Algorithmic Foundations of Machine Learning

   Grants (PI Only)

  • National Natural Science Foundation of China (NSFC) General Program, NSFC, 2025-2028
  • Xiangjiang Laboratory General Project, 2022-2024
  • Hunan Provincial Natural Science Foundation Youth Program, Hunan Provincial Department of Science and Technology, 2021-2023
  • National Natural Science Foundation of China (NSFC) Youth Program, NSFC, 2019-2021

   Recent Publication

                  DBLP

    Journal Articles

  • Xiaoliang Wu, Feng Shi*, Yutian Guo, Zhen Zhang, Junyu Huang, Jianxin Wang: An approximation algorithm for lower-bounded k-median with constant factor. SCIENCE CHINA Information Sciences 65(4) (2022). (CCF A)
  • Feng Shi, Hangcheng Li, Guozhen Rong, Zhen Zhang, Jianxin Wang: Improved Fixed-parameter Algorithm for the Tree Containment Problem on Unrooted Phylogenetic Network, IEEE/ACM Transactions on Computational Biology and Bioinformatics, 19(6): 3539-3552 (2022). (CCF B)
  • Feng Shi, Frank Neumann, Jianxin Wang: Time complexity analysis of evolutionary algorithms for 2-hop (1,2)-minimum spanning tree problem, Theoretical Computer Science, 893: 159-175 (2021) (CCF B)
  • Feng Shi, Jie You, Zhen Zhang, Jingyi Liu, Jianxin Wang: Fixed-parameter tractability for the Tree Assembly problem. Theoretical Computer Science 886:3-12 (2021) (CCF B)
  • Zhen Zhang, Yutian Guo, Junyu Huang, Jianxin Wang, Feng Shi*: Improved approximation for prize-collecting red-blue median. Theoretical Computer Science 878-879:67-82 (2021) (CCF B)
  • Feng Shi, Frank Neumann, Jianxin Wang: Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem. Algorithmica 83:906-939 (2021) (CCF B)
  • Jie You, Feng Shi, Jianxin Wang, Qilong Feng: Fixed-parameter tractability for minimum tree cut/paste distance and minimum common integer partition. Theoretical Computer Science 806: 256-270 (2020) (CCF B)
  • Mojgan Pourhassan, Feng Shi, Frank Neumann: Parameterized Analysis of Multiobjective Evolutionary Algorithms and the Weighted Vertex Cover Problem. Evolutionary Computation 27(4): 559-575 (2019) (CCF B)
  • Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neumann: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. Algorithmica 81(2): 828-857 (2019) (CCF B)
  • Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang: A parameterized algorithm for the Maximum Agreement Forest problem on multiple rooted multifurcating trees. Journal of Computer and System Sciences 97: 28-44 (2018) (CCF B)
  • Jianer Chen, Feng Shi, Jianxin Wang: Approximating Maximum Agreement Forest on Multiple Binary Trees, Algorithmica 76(4): 867-889 (2016) (CCF B)
  • Feng Shi, Qilong Feng, Jie You, Jianxin Wang: Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees, Journal of Combinatorial Optimization 32(1): 111-143 (2016)
  • Feng Shi, Jianxin Wang, Yufei Yang, Qilong Feng, Weilong Li, Jianer Chen: A fixed-parameter algorithm for the maximum agreement forest problem on multifurcating trees. SCIENCE CHINA Information Sciences 59(1): 1-14 (2016) (CCF A)
  • Jie You, Jianxin Wang, Qilong Feng, Feng Shi: Kernelization and parameterized algorithms for covering a tree by a set of stars or paths. Theoretical Computer Science 607: 257-270 (2015) (CCF B)
  • Jianxin Wang, Weimin Su, Min Yang, Jiong Guo, Qilong Feng, Feng Shi, Jianer Chen: Parameterized complexity of control and bribery for d-approval elections. Theoretical Computer Science 595: 82-91 (2015) (CCF B)
  • Feng Shi, Jianxin Wang, Jianer Chen, Qilong Feng, Jiong Guo: Algorithms for parameterized maximum agreement forest problem on multiple trees. Theoretical Computer Science 554: 207-216 (2014) (CCF B)
  • Feng Shi, Qilong Feng, Jianer Chen, Lusheng Wang, Jianxin Wang: Distances Between Phylogenetic Trees: A Survey. Tsinghua Science and Technology 18(5): 490-499 (2013)

    • Conference Papers

  • Xiankun Yan, Anh Viet Do, Feng Shi, Xiaoyu Qin, Frank Neumann: Optimizing Chance-Constrained Submodular Problems with Variable Uncertainties. ECAI 2023: 2826-2833. (CCF B)
  • Guangwei Wu, Fu Zuo, Feng Shi, Jianxin Wang: Applying Johnson's Rule in Scheduling Multiple Parallel Two-Stage Flowshops. IJTCS-FAW 2023: 212-224.
  • Feng Shi, Jie You, Zhen Zhang, Jingyi Liu: Tractabilities for Tree Assembly Problems. TAMC 2020: 300-312
  • Feng Shi, Frank Neumann, Jianxin Wang: Runtime analysis of evolutionary algorithms for the depth restricted (1, 2)-minimum spanning tree problem. FOGA 2019: 133-146
  • Qilong Feng, Zhen Zhang, Feng Shi, Jianxin Wang: An Improved Approximation Algorithm for the k-Means Problem with Penalties. FAW 2019: 170-181
  • Feng Shi, Frank Neumann, Jianxin Wang: Runtime analysis of randomized search heuristics for the dynamic weighted vertex cover problem. GECCO 2018: 1515-1522 (CCF C)
  • Feng Shi, Martin Schirneck, Tobias Friedrich, Timo Kötzing, Frank Neumann: Reoptimization times of evolutionary algorithms on linear functions under dynamic uniform constraints. GECCO 2017: 1407-1414 (CCF C)
  • Mojgan Pourhassan, Feng Shi, Frank Neumann: Parameterized Analysis of Multi-objective Evolutionary Algorithms and the Weighted Vertex Cover Problem. PPSN 2016: 729-739 (CCF B)
  • Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang: Approximation Algorithms for Maximum Agreement Forest on Multiple Trees. COCOON 2014: 381-392
  • Feng Shi, Jie You, Qilong Feng: Improved Approximation Algorithm for Maximum Agreement Forest of Two Trees. FAW 2014: 205-215
  • Jie You, Qilong Feng, Jiong Guo, Feng Shi: On Star-Cover and Path-Cover of a Tree. FAW 2014: 298-308
  • Feng Shi, Jianer Chen, Qilong Feng, Jianxin Wang: Parameterized Algorithms for Maximum Agreement Forest on Multiple Trees. COCOON 2013: 567-578

   Professional Services

    Conference PC Member

  • GECCO 2020-2023 (Theory Track)
  • CEC 2023 (Theory Track)
  • IJCAI-PRICAI 2020
  • ICPCSEE 2019
  • GECCO 2017 (Student Workshop)

    • Journal Reviewer

  • Journal of Computer and System Sciences
  • Algorithmica
  • Theoretical Computer Science
  • Journal of Combinatorial Optimization
  • Frontier of Computer Science

    • Conference Reviewer

  • GECCO, ISBRA, SODA, WADS, WG, COCOON, TAMC

   Teaching Activities

  • Spring 2021-2023, Data Structure (undergraduates)
  • Spring 2022-2023, Graph Theory and Combinatorics (undergraduates and graduates)
  • Autumn 2021-2023, Analysis and Design of Algorithm (undergraduates)
  • Autumn 2021-2022, Artificial Intelligence (Postgraduates and PhD candidates, in English)
  • Autumn 2020, C Programming Language (undergraduates)
  • Spring 2019-2020, Artificial Intelligence (Postgraduates and PhD candidates, in English)