Near-Optimal Solutions for Combinatorial Problems: Algorithms and Complexity

组合优化问题的近似算法的研究可以追溯到20世纪60年代，尽管这一领域受到了极大的关注，但直到最近几年才有了很大的进展。最近，在近似算法的设计和分析方面，以及更重要的是，在提供证据的技术方面，已经有了一些重要的突破，这些技术引入了新技术，这些技术证明问题没有有效的算法来保证特定性能保证的接近最佳解决方案。研究的问题包括：(a)顶点覆盖问题；(b)最大无环子图问题；(c)最低成本满意度问题；(d) Steiner树问题；(e)旅行商问题；(f)装箱问题；(g)图划分问题；(h)几个调度问题。在为这些问题寻找改进的近似算法时，主要关注的是在算法的设计和分析中依赖于使用线性规划作为工具的方法。此外，这些证明非近似结果的新技术应用于各种设置；特别是：(1)证明近似算法的绝对误差的下界（相对于相对误差）；(2)加强下界（传统方法能够证明下界与最知名的近似算法的性能不匹配）。

The study of approximation algorithms for combinatorial optimization problems dates back to the 1960's, and in spite of significant attention paid to this area, there has not been much progress until the past few years. Recently, there have been a number of important breakthroughs that have introduced new techniques, both in the design and analysis of approximation algorithms, and more significantly, in techniques for providing evidence that problems do not have efficient algorithms that guarantee near-optimal solutions for particular performance guarantees. The problems studied include: (a) the vertex cover problem; (b) the maximum acyclic subgraph problem; (c) the minimum-cost satisfiability problem; (d) the Steiner tree problem; (e) the traveling salesman problem; (f) the bin-packing problem; (g) the graph partitioning problem; and (h) several scheduling problems. In the search for improved approximation algorithms for these problems, the primary focus is on methods that rely on the use of linear programming as a tool both in the design and the analysis of the algorithm. Also these new techniques for proving nonapproximability results are applied in a variety of settings; in particular: (1) proving lower bounds on the absolute error of approximation algorithms (as opposed to the relative error); and (2) strengthening lower bounds (where traditional methods were able to prove lower bounds that did not match the performance of the best known approximation algorithms).