New directions in Approximation Algorithms for NP-hard problems

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

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.