AF: Small: Approximate optimization: Algorithms, Hardness, and Integrality Gaps

AF：小：近似优化：算法、硬度和完整性差距

• 批准号: 1526092
• 负责人: Venkatesan Guruswami
• 金额: $ 25万
• 依托单位: Carnegie-Mellon University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2015
• 资助国家: 美国
• 起止时间: 2015-09-01 至 2019-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1526092&HistoricalAwards=false
• 关键词: AF; Small; Approximate; optimization; Algorithms

Optimization problems, where the goal is to find a solution subject to some constraints that maximizes or minimizes a certain objective value, are ubiquitous in computing. As an overwhelming majority of optimization problems are NP-hard to solve optimally, one widely studied approach is to settle for approximately optimal solutions with provable guarantees on quality. The overarching goal in the theory of approximate optimization is to identify, for broad classes of optimization problems, the best approximation factor achievable efficiently. This study has two sides that go hand-in-hand, the design of efficient approximation algorithms, and complementary hardness results establishing limits to the best approximation possible. One of the most widely employed approaches to design approximation algorithms is via convex programming relaxations such as linear or semidefinite programs. So a third intertwined aspect is to understand the power and limitations of such tools for important optimization problems. Research on this topic has made huge strides, and for a broad class of problems called constraint satisfaction problems, a common meeting ground of all these aspects has been uncovered, in the form of a canonical semidefinite program achieving the best possible approximation ratio in a unified manner. This theory, however, relies on the unproven Unique Games Conjecture (UGC), and also doesn't extend to various other important settings. This project focuses on a carefully conceived collection of fundamental research directions that are germane given our current understanding of the approximability landscape. Topics studied will include approaches to bypass the reliance on the UGC where possible, the complexity of approximately solving problems where a perfectly satisfying assignment exists (a setting that is not at all captured by the UGC), and a promising new direction where the notion of approximation is not in the number of constraints satisfied but rather in how strongly the constraints are satisfied. The project will aim to advance the frontiers of the subject by harnessing the confluence of the three aspects: algorithms, hardness, and mathematical programming, that together bear upon this rich subject. In particular, the project will investigate the power of semidefinite programs in certifying properties of random graphs and matrices, as well as their limitations in the form of integrality gaps as prognosis of the intractability of problems whose status is otherwise open or only known under the UGC.The proposed research will shed light on the approximability of basic optimization problems that abstract some of the core computational tasks arising in practice. The research and outreach activities will aim to foster a cross-fertilization of ideas between the approximation and constraint satisfaction communities. On the education front, the project will train and mentor graduate students and provide a stimulating research environment for them. The research will balance the long term and general agenda of advancing the frontiers of the subject with the investigation of precisely stated open questions that are yet to receive the thorough investigation they deserve. The research findings, as appropriate, will be integrated into a novel course highlighting the emerging confluence of algorithms, hardness results, and integrality gaps.

优化问题是计算中普遍存在的问题，其目标是在一定的约束条件下找到一个使某一目标值最大化或最小化的解。由于绝大多数优化问题都是NP-困难的最优问题，一种被广泛研究的方法是在质量上有可证明的保证的近似最优解。近似最优化理论的首要目标是，对于大类优化问题，找出可有效实现的最佳逼近因子。这项研究有两个方面，一是设计有效的近似算法，二是互补的困难结果，建立了可能的最佳近似的限制。设计近似算法最广泛使用的方法之一是通过凸规划松弛，例如线性或半定规划。因此，第三个相互交织的方面是了解这些工具在解决重要优化问题时的能力和局限性。关于这一主题的研究已经取得了巨大的进展，对于一大类被称为约束满足问题的问题，所有这些方面的公共交汇点已经被发现，以规范的半定程序的形式在统一的方式下获得可能的最佳逼近比。然而，这一理论依赖于未经证实的独特游戏猜想(UGC)，也不能扩展到其他各种重要的设置。这个项目专注于精心构思的基础研究方向的集合，这些方向与我们目前对可近似性图景的理解是密切相关的。所研究的主题将包括在可能的情况下绕过对教资会的依赖的方法，在存在完全令人满意的作业的情况下近似解决问题的复杂性(教资会根本没有捕捉到的设置)，以及一个有希望的新方向，其中近似的概念不是取决于满足的约束的数量，而是满足约束的程度。该项目的目标是通过利用算法、难度和数学编程这三个方面的融合来推进该学科的前沿，这三个方面共同影响着这一丰富的学科。特别是，该项目将调查半定程序在证明随机图和矩阵的性质方面的能力，以及它们以完整性间隙的形式作为预测问题的难解性的局限性，这些问题的状态在其他方面是公开的或仅根据UEg.所提出的研究将阐明抽象实践中出现的一些核心计算任务的基本优化问题的可近似性。研究和外联活动的目的是促进近似界和约束满足界之间的思想交流。在教育方面，该项目将培训和指导研究生，并为他们提供一个鼓舞人心的研究环境。这项研究将平衡推进这一主题前沿的长期和总体议程与对尚未得到应有的彻底调查的确切陈述的未决问题的调查。研究结果将被适当地整合到一门新的课程中，强调算法、困难结果和完整性差距的新融合。