New directions in Approximation Algorithms for NP-hard problems

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

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.