Near-Optimal Solutions for Combinatorial Problems: Algorithms and Complexity

点击翻译按钮获取中文摘要

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).