New directions in Approximation Algorithms for NP-hard problems

NP 难题近似算法的新方向

• 批准号: 0514993
• 负责人: Sanjeev Arora
• 金额: $ 20万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2005
• 资助国家: 美国
• 起止时间: 2005-07-15 至 2007-06-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0514993&HistoricalAwards=false
• 关键词: New; directions; Approximation; Algorithms; NP

Many optimization problems are NP-hard, and computing approximate solutions is an attractive way to cope with NP-hardness. The effort to understand the approximation properties of NP problems has occupied the center stage of theoretical computer science in the past decade. Despite many successes in this field, the status of some of the basic problems ---- metric tsp, vertex cover, graph coloring, sparsest cut etc.---is still open. The project consists of designing new approaches for computing approximate solutions to these problems. Any results for these central problems should generalize to many other problems.The tools used involve sophisticated geometric arguments, and "lift and project" technique from polyhedral combinatorics. Another goal is to develop a comprehensive framework for designing approximation algorithms without relying on semidefinite programming (SDP). Many recent approximation algorithmsuse SDP, which is not particularly efficient in practice. The goal in this project is to replace SDP with simpler algorithms based upon eigenvalue computations. Another aspect of the project is to prove lowerbounds to complement any new algorithms, or to rule out the existence of some of the above algorithms. The lowerbounds attempted would be both for all polynomial-time algorithms ---this would use PCPs---and for specific algorithms arising from lift and project methods. (The latter consists of viewing lift and project methods as a weak computational model.) Broader impact of this project include dissemination efforts such as new innovative courses in graduate and undergraduate education, new text book, and survey articles on current research.

许多优化问题都是np困难的，计算近似解是处理np困难的一种有吸引力的方法。在过去的十年中，理解NP问题的近似性质的努力占据了理论计算机科学的中心舞台。尽管在这一领域取得了许多成功，但一些基本问题（---- metric tsp，顶点覆盖，图着色，最稀疏切割等）的现状仍然是开放的。该项目包括设计计算这些问题近似解的新方法。这些中心问题的任何结果都应该推广到许多其他问题。使用的工具包括复杂的几何参数，以及多面体组合中的“提升和投影”技术。另一个目标是开发一个全面的框架来设计不依赖于半定规划（SDP）的近似算法。最近的许多近似算法都使用了SDP，但在实践中并不是特别有效。这个项目的目标是用基于特征值计算的更简单的算法取代SDP。该项目的另一个方面是证明下限以补充任何新算法，或者排除上述某些算法的存在。尝试的下限既适用于所有多项式时间算法（这将使用pcp），也适用于由升降机和项目方法产生的特定算法。（后者将升降机和工程方法视为弱计算模型。）该项目的更广泛影响包括传播工作，如研究生和本科生教育的新创新课程，新教科书和当前研究的调查文章。