Near-Optimal Solutions for Combinatorial Problems: Algorithms and Complexity

组合问题的近乎最优解：算法和复杂性

• 批准号: 9307391
• 负责人: David Shmoys
• 金额: --
• 依托单位: Cornell University
• 依托单位国家: 美国
• 项目类别: Continuing grant
• 财政年份: 1994
• 资助国家: 美国
• 起止时间: 1994-04-01 至 1998-03-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=9307391&HistoricalAwards=false
• 关键词: Near; Optimal; Solutions; Combinatorial; Problems

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

组合优化问题的逼近算法的研究可以追溯到上世纪60年代的S，尽管这一领域引起了人们的极大关注，但直到最近几年才有了很大的进展。最近，在近似算法的设计和分析方面，以及更重要的是，在提供证据表明问题不具有保证特定性能保证的近最优解的有效算法的技术方面，已经有了一些重要的突破。所研究的问题包括：(A)顶点覆盖问题；(B)最大非循环子图问题；(C)最小代价可满足性问题；(D)Steiner树问题；(E)旅行商问题；(F)装箱问题；(G)图划分问题；(H)几个调度问题。在为这些问题寻找改进的近似算法时，主要关注的是在算法的设计和分析中依赖于使用线性规划作为工具的方法。此外，这些用于证明不可逼近结果的新技术被应用于各种设置；尤其是：(1)证明近似算法的绝对误差的下界(相对于相对误差)；以及(2)加强下界(其中传统方法能够证明与最著名的近似算法的性能不匹配的下界)。