New Directions in Semidefinite Programming and Approximation

半定规划和逼近的新方向

• 批准号: 0830673
• 负责人: Sanjeev Arora
• 金额: --
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2011-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830673&HistoricalAwards=false
• 关键词: New; Directions; Semidefinite; Programming; Approximation

Computing approximate solutions to NP-hard optimization problems is an idea that is attractive both in theory and practice. Semidefinite programming (SDP) has become an indispensable tool in this area. It has led to new and better algorithms, and recently, thanks in part to the PI's prior work, more combinatorial algorithms that actually avoid SDP. The connections of SDP to high-dimensional geometry, metric embeddings, fourier transforms, and probabilistically checkable proofs are also at the center of some of the exciting work in theoretical computer science in recent years.The project will work on ideas to (a) apply SDP to design new approximation algorithms for a host of problems, such as graph coloring, metric traveling salesman, graph partitioning, vertex cover; (b) use insights from SDP to design efficient combinatorial algorithms; (c) apply SDP insights (and a ``constructive'' version of SDP duality discovered recently by the PI and his student) to new settings such as decoding error-correcting codes, compressed sensing, and analysing network algorithms and swarm algorithms; (d) explore connections between SDPs, high-dimensional geometry, fourier transforms, and probabilistically checkable proofs.SDP-inspired primal-dual approaches are an important new extension of traditional approaches based upon linear-programming duality, and developing their uses promises to have transformative impact. Development of new approximation algorithms for central problems like graph partitioning and metric TSP may also transform the field.During this project new courses will be designed at the undergraduate and graduate level to teach these new ideas in an accessible way.

计算 NP 难优化问题的近似解是一个在理论和实践上都很有吸引力的想法。 半定规划（SDP）已成为该领域不可或缺的工具。它催生了新的、更好的算法，最近，部分归功于 PI 之前的工作，更多的组合算法实际上避免了 SDP。 SDP 与高维几何、度量嵌入、傅立叶变换和概率可检查证明的联系也是近年来理论计算机科学中一些令人兴奋的工作的核心。该项目将致力于 (a) 应用的想法SDP为一系列问题设计新的近似算法，例如图着色、度量旅行商、图分区、顶点覆盖； (b) 利用 SDP 的见解来设计有效的组合算法； (c) 将 SDP 见解（以及 PI 及其学生最近发现的 SDP 对偶性的“建设性”版本）应用于新设置，例如解码纠错码、压缩感知以及分析网络算法和群体算法； (d) 探索 SDP、高维几何、傅里叶变换和概率可检查证明之间的联系。受 SDP 启发的原对偶方法是基于线性规划对偶性的传统方法的重要新扩展，并且开发其用途有望变革性的影响。针对图划分和度量 TSP 等核心问题开发新的近似算法也可能会改变该领域。在该项目期间，将为本科生和研究生设计新课程，以一种易于理解的方式教授这些新思想。