组合优化若干经典问题新进展

New perspectives of several fundamental problems in combinatorial optimization

组合优化是20世纪中后期发展起来的一个运筹学与计算机科学交叉学科分支,研究具有离散结构的优化问题解的性质和求解方法.由于不同离散问题的结构差异,出现了各种各样的研究手段和技巧.针对组合优化的若干经典问题,简述了算法和复杂性理论的研究进展.

Combinatorial optimization, as an interdiscipline of operations research and computer science, has been developing since the mid-20th century. It characters opti- mization problems with discrete structures, and explores their solution methods. Due to the structural divergence in discrete problems, there has been a wide variety of method- ologies and techniques. In this paper, we briefly introduce a number of fundamental problems in combinatorial optimization, and present the recent achievements together with some open problems.