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

职业：近似 NP 难问题 - 高效算法及其局限性

• 批准号: 1343104
• 负责人: Prasad Raghavendra
• 金额: $ 39.45万
• 依托单位: University of California-Berkeley
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-12-01 至 2016-12-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1343104&HistoricalAwards=false
• 关键词: CAREER; Approximating; NP; Hard; Problems

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.

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