Efficiently solvable special cases of hard combinatorial optimization problems
Efficiently solvable special cases of hard combinatorial optimization problems
复制标题
硬组合优化问题的可有效解决的特殊情况
DOI：
10.1007/bf02614311
复制
发表时间：
1997
影响因子：
2.7
通讯作者：
R. Burkard
中科院分区：
文献类型：
--
作者：
R. Burkard
我们调查领域的多项式可解的特殊情况下，硬组合优化问题，如旅行推销员问题，二次分配问题和斯坦纳树问题的一些最新进展。这种特殊情况可以通过考虑特殊的成本结构，问题的几何形状，底层图结构的特殊拓扑结构或通过分析特殊算法来找到。我们特别强调识别算法的重要性。我们评论在这方面的开放性问题，并概述了在这一领域的未来研究的一些路线。
We survey some recent advances in the field of polynomially solvable special cases of hard combinatorial optimization problems like the travelling salesman problem, quadratic assignment problems and Steiner tree problems. Such special cases can be found by considering special cost structures, the geometry of the problem, the special topology of the underlying graph structure or by analyzing special algorithms. In particular we stress the importance of recognition algorithms. We comment on open problems in this area and outline some lines for future research in this field.