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），并且也没有扩展到其他各种重要的设置。该项目侧重于精心设计的一系列基础研究方向，这些方向与我们目前对近似性景观的理解密切相关。研究的主题将包括尽可能绕过对 UGC 的依赖的方法、在存在完全令人满意的作业的情况下近似解决问题的复杂性（UGC 根本没有捕获的设置）以及一个有前途的新方向，其中近似不在于满足的约束的数量，而在于满足约束的强度。该项目旨在通过利用算法、硬度和数学编程这三个方面的融合来推进该学科的前沿，这三个方面共同影响着这个丰富的学科。特别是，该项目将研究半定程序在证明随机图和矩阵的属性方面的能力，以及它们以完整性差距形式的局限性，作为对状态未公开或仅在 UGC 下已知的问题的棘手性的预测所提出的研究将揭示基本优化问题的近似性，这些问题抽象了实践中出现的一些核心计算任务。研究和推广活动旨在促进近似满足社区和约束满足社区之间思想的交叉交流。 在教育方面，该项目将培训和指导研究生，并为他们提供一个激励性的研究环境。该研究将平衡推进该学科前沿的长期和总体议程与对尚未得到应有的彻底调查的明确陈述的开放问题的调查。研究结果将酌情整合到一门新颖的课程中，强调算法、硬度结果和完整性差距的新兴融合。