Near-Optimal Solutions for Combinatorial Problems: Algorithms and Complexity

组合优化问题的近似算法的研究可以追溯到20世纪60年代，尽管对这一领域给予了极大的关注，但直到过去几年才取得了很大的进展。 最近，已经有一些重要的突破，引进了新的技术，无论是在设计和分析的近似算法，更重要的是，在技术提供证据的问题没有有效的算法，保证接近最优的解决方案，为特定的性能保证。 所研究的问题包括：（a）顶点覆盖问题，（B）最大无圈子图问题，（c）最小费用可满足性问题，（d）最小费用可满足性问题。 (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).