CAREER: Approximating NP-Hard Problems -Efficient Algorithms and their Limits

绝大多数规划或设计任务都涉及优化问题，寻求最小化所提出的解决方案的成本，或最大化其效率或回报。 通常，目标是从一组有限的离散选项中识别最优解（组合优化）。 不幸的是，绝大多数优化问题的精确解在计算上是难以处理的。 为了科普这个难题，人们通常会采用可证明近似最优解的算法。下面的问题自然源于近似的概念：对于给定的组合优化问题，可以有效计算的最优解的最佳近似是什么？有两个方面来回答上述问题：设计近似算法，并表明没有有效的算法可以提供更好的近似保证（硬度结果）。这两个看似不同的方面的融合是近年来理论计算机科学中最令人兴奋的发展之一。这个项目将涉及改进的近似算法的设计，以及显示这些算法基本上是最佳的。虽然近似算法的设计是一个广阔的研究领域，但绝大多数现有近似算法的主要工具是凸优化技术，如线性或半定规划。现有的算法技术在大量的基本组合优化问题上遇到了一个共同的障碍，这个障碍被诱人的“独特游戏猜想（UGC）”所封装。“因此，近似性的研究正处于一个非常令人兴奋的时刻。一方面，对UGC的肯定将解决长期悬而未决的问题，展示组合优化问题的潜在统一性，更重要的是，表明最简单的半定程序产生最佳近似。另一方面，反驳UGC将导致新的算法技术，最终导致更好的近似算法。PI提出了一系列研究问题，涉及近似算法的设计和近似结果的硬度。大体而言，该项目有以下四个研究主题：1）通过新算法的设计和完整性缺口示例的构造来理解半定规划层次结构的力量。2）将UGC下的近似性的新兴框架扩展到更大类的组合优化问题。3）开发技术机器和小工具来无条件地显示基于UGC的一些困难结果，朝着其解决方案取得进展。4）将近似困难中开发的分析工具应用于理论计算机科学的其他分支，例如约束满足问题的精确算法的研究。这项研究必须借鉴各种理论学科的工具，例如编码理论，属性测试，计算学习，去随机化和离散谐波分析。该研究在科学研讨会，研究生课程的开发，关于近似最新研究的讲义和调查文章，促进本科生研究和为博士生提供建议方面具有更广泛的影响力。

The vast majority of planning or design tasks involves an optimization problem, seeking to either minimize the cost of the proposed solution, or maximize its efficiency or payoff. Often, the goal would be the identification of the optimal solution from a set of finite many discrete options (combinatorial optimization). Unfortunately, an exact solution for the overwhelming majority of optimization problems turns out to be computationally intractable. To cope with intractability, one often settles for algorithms that provably approximate the optimal solution. The following question stems naturally from the notion of approximation: For a given combinatorial optimization problem, what is the best approximation to the optimal solution that can be efficiently computed?There are two facets to answering the above question: designing approximation algorithms and showing that no efficient algorithm can provide a better approximation guarantee (hardness result). The convergence of these two seemingly different facets has been one of the most exciting developments in theoretical computer science in recent years. This project would involve the design of improved approximation algorithms as well as showing that these algorithms are essentially optimal. Although the design of approximation algorithms is a vast area of research, the main tool underlying an overwhelming majority of existing approximation algorithms is a convex optimization technique such as linear or semidefinite programming. Existing algorithmic techniques have hit upon a common barrier on a large number of fundamental combinatorial optimization problems, a barrier that is encapsulated by the tantalizing "Unique Games Conjecture (UGC)." Therefore the study of approximability is at a very exciting juncture. On one hand, an affirmation of the UGC would resolve long standing open questions , demonstrate an underlying unity in combinatorial optimization problems, and, more importantly, show that the simplest semidefinite programs yield the best approximations. On the other hand, disproving the UGC would lead to new algorithmic techniques that will eventually lead to better approximation algorithms.The PI proposes a set of research questions involving both design of approximation algorithms and hardness of approximation results. Broadly speaking, the project has the following four research themes:1) Understand the power of semidefinite programming hierarchies via the design of new algorithms and constructions of integrality gap examples.2) Extend the emerging framework of approximability under the UGC to a larger class of combinatorial optimization problems.3) Develop technical machinery and gadgets to show unconditionally some of the hardness results based on the UGC, making progress towards its resolution.4) Apply the analytic tools developed in hardness of approximation to other branches of theoretical computer science, such as the study of exact algorithms for constraint satisfaction problems.This research necessarily draws upon tools from various theoretical disciplines such as coding theory, property testing, computational learning, derandomization and discrete harmonic analysis. The research has a strong potential for broader impact in terms of scientific workshops, developement of graduate courses, lecture notes and survey articles on the latest research in approximation, promoting undergraduate research, and advising Ph.D students.