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.