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

绝大多数计划或设计任务都涉及优化问题，寻求最小化所建议的解决方案的成本，或最大化其效率或收益。通常，目标是从一组有限的许多离散选项中识别出最优解（组合优化）。不幸的是，绝大多数优化问题的精确解决方案在计算上是难以处理的。为了解决棘手的问题，人们通常会选择可证明接近最优解的算法。下面的问题自然源于近似的概念：对于给定的组合优化问题，可以有效计算的最优解的最佳近似是什么？回答上述问题有两个方面：设计近似算法和证明没有有效的算法可以提供更好的近似保证（硬度结果）。这两个看似不同的方面的融合是近年来理论计算机科学中最令人兴奋的发展之一。这个项目将涉及改进的近似算法的设计，以及显示这些算法本质上是最优的。虽然近似算法的设计是一个广阔的研究领域，但绝大多数现有近似算法的主要工具是凸优化技术，如线性或半定规划。现有的算法技术在许多基本的组合优化问题上遇到了一个共同的障碍，这个障碍被诱人的“独特游戏猜想”（Unique Games Conjecture， 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.