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中已知的问题。拟议的研究将揭示基本优化问题的近似优化性，这些问题涉及一些核心计算的核心计算任务的近似性问题。研究和外展活动将旨在促进近似和约束满意度社区之间思想的交叉侵占。 在教育方面，该项目将培训和指导研究生，并为他们提供刺激性的研究环境。这项研究将平衡长期和一般议程，即对主题的前沿进行推进，并调查精确的开放问题，这些问题尚未得到应有的彻底调查。根据适当的研究结果将集成到一个新的课程中，强调算法，硬度结果和整体差距的新兴汇合。