CAREER: Optimal Approximability

职业：最佳逼近性

• 批准号: 0747250
• 负责人: Ryan O'Donnell
• 金额: $ 40万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-03-01 至 2014-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0747250&HistoricalAwards=false
• 关键词: CAREER; Optimal; Approximability

The PI proposes to study constraint satisfaction problems likeMax-Cut, Max-2-Sat, Vertex-Cover, and Chromatic-Number. For many ofthese problems, the boundary between efficiently-achievableapproximation ratios and NP-hard approximation ratios is unknown. ThePI has a 3-point plan to determine these boundaries:1. Use recent connections between semidefinite programming algorithms,integrality gaps, and property testing to determine preciseboundaries, assuming the "Unique Games Conjecture."2. Define and explore new, more efficient property-testing--basedhardness reductions.3. Prove the Unique Games Conjecture, using the newproperty-testing--based reductions along with ideas from the theory ofParallel Repetition.The broader goal of this line of research is to give more efficientand more effective algorithms for the fundamental algorithmic taskslike network partitioning, constraint satisfaction, and optimization.The PI will explore the limits of how well efficient algorithms cansolve these problems. Proving "hardness results" or limitations onthe capabilities of efficient computation has positive practicalconsequences. For one, it prevents wasted effort in trying to improveunimprovable algorithms. More importantly, by carefully isolating theaspects of algorithmic tasks which make them difficult, we are oftenled to new, effective algorithms for solving the tasks when theseaspects are not present.

PI建议研究约束满足问题，如最大割、最大2-饱和、顶点覆盖和色数。对于许多这样的问题，有效可达逼近比和NP-Hard逼近比之间的边界是未知的。PI有一个三点计划来确定这些边界：1.使用半定编程算法、完整性差距和属性测试之间的最近联系来确定精确边界，假设“唯一的游戏猜想”。2.定义和探索新的、更有效的属性测试--基于硬度降低。使用新的基于属性测试的约简和并行重复理论的思想来证明唯一的游戏猜想。这一研究的更广泛的目标是给出更有效和更有效的算法来完成基本的算法任务，如网络划分、约束满足和优化。PI将探索高效算法解决这些问题的限度。证明“硬性结果”或对有效计算能力的限制具有积极的实际意义。首先，它防止了在试图改进不能改进的算法时浪费精力。更重要的是，通过仔细地隔离算法任务中使它们变得困难的方面，我们经常被引导到新的、有效的算法来解决当这些任务不存在的情况下的任务。