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也可能改变该领域。在这个项目中，新的课程将设计在本科生和研究生水平，以方便的方式教授这些新的想法。