AF: Small: Mathematical Programming Methods in Approximation

AF：小：近似数学规划方法

• 批准号: 0916218
• 负责人: Moses Charikar
• 金额: $ 50万
• 依托单位: Princeton University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2009
• 资助国家: 美国
• 起止时间: 2009-08-15 至 2013-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0916218&HistoricalAwards=false
• 关键词: AF; Small; Mathematical; Programming; Methods

Mathematical programming techniques like linear programming and semidefinite programming have firmly established themselves as valuable tools in the approximation algorithm design toolkit. They are often used as tractable relaxations to hard combinatorial optimization problems and as design guides to obtain approximation algorithms. This project attempts to enhance our understanding of the strengths and weaknesses of mathematical programming techniques for several fundamental optimization problems and proposes to investigate general methods to strengthen our currently known mathematical programming techniques.The broad goals of this project are the following: (a) Attempt to devise better algorithms for unique games ? a constraint satisfaction problem that is known to capture the limitations of current semidefinite programming methods used in approximation algorithms. Beating the current best algorithms will necessarily involve developing new techniques that overcome the limitations of current SDP approaches. (b) Understand the structure of strengthened relaxations obtained by lift-and-project procedures and develop techniques to exploit the additional information provided by these stronger relaxations to obtain better approximation algorithms. (c) Work towards closing large gaps in our understanding of the approximability of fundamental optimization problems.Successfully achieving the project goals will entail significant advances in the state of the art for approximation algorithms. The research could potentially develop tools and techniques with broad applicability to several optimization problems. Course materials for graduate and undergraduate courses will be developed distilling research results of this project, as well as new developments in the field.

数学规划技术，如线性规划和半夜场编程已牢固地确立了自己作为逼近算法设计工具包中的有价值的工具。它们经常被用作难组合优化问题的易于处理的松弛，并作为设计指南，以获得近似算法。这个项目试图提高我们的理解的优势和弱点的数学规划技术的几个基本的优化问题，并提出调查一般的方法，以加强我们目前已知的数学规划technologies.The广泛的目标，这个项目是：（一）试图设计更好的算法独特的游戏？一个约束满足问题，是已知的捕捉当前的半夜场编程方法中使用的近似算法的局限性。击败目前最好的算法将必然涉及开发新的技术，克服目前的SDP方法的局限性。 (b)理解通过提升和投影程序获得的强化弛豫的结构，并开发技术来利用这些更强的弛豫提供的额外信息，以获得更好的近似算法。 (c)努力缩小我们对基本优化问题的可逼近性的理解中的巨大差距。成功实现项目目标将需要近似算法的最新技术水平的显著进步。这项研究可能会开发出广泛适用于几个优化问题的工具和技术。研究生和本科课程的教材将开发蒸馏本项目的研究成果，以及在#64257;领域的新发展。