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

优化问题在计算中无处不在，其目标是在某些约束条件下找到最大化或最小化某个目标值的解决方案。由于绝大多数优化问题都是np困难的最优解，一个被广泛研究的方法是解决具有可证明质量保证的近似最优解。近似优化理论的首要目标是识别，对于广泛的优化问题，可有效实现的最佳近似因子。本研究有两个方面，一个是设计有效的近似算法，另一个是确定最佳近似可能的极限的互补硬度结果。设计近似算法最广泛使用的方法之一是通过凸规划松弛，如线性或半定规划。因此，第三个相互交织的方面是了解这些工具在解决重要优化问题时的能力和局限性。对这一主题的研究已经取得了巨大的进步，对于一个被称为约束满足问题的广泛类别的问题，所有这些方面的一个共同的共同点已经被发现，以一个规范的半确定规划的形式，以统一的方式实现最佳可能的近似比。然而，这一理论依赖于未经证实的独特游戏猜想（Unique Games Conjecture， UGC），并且也不能扩展到其他重要的场景中。该项目侧重于精心构思的基础研究方向的集合，这些方向与我们目前对近似性景观的理解密切相关。研究课题将包括在可能的情况下绕过对教资会的依赖的方法，在存在完全令人满意的作业的情况下近似解决问题的复杂性（教资会根本没有考虑到这种情况），以及一个有希望的新方向，即近似的概念不在于满足约束的数量，而在于满足约束的强度。该项目旨在通过利用算法、硬度和数学规划这三个方面的融合来推进这一学科的前沿，这三个方面共同影响着这一丰富的学科。特别是，该项目将研究半确定程序在证明随机图和矩阵性质方面的能力，以及它们在完整性缺口形式方面的局限性，作为预测问题的难解性，这些问题的状态是公开的或仅在UGC下已知。提出的研究将揭示基本优化问题的近似性，抽象了一些在实践中出现的核心计算任务。研究和推广活动的目的是促进近似满足和约束满足社区之间的思想交流。在教育方面，该项目将培训和指导研究生，并为他们提供一个刺激的研究环境。这项研究将平衡推进该学科前沿的长期和总体议程，以及对尚未得到应有的彻底调查的精确陈述的开放性问题的调查。研究结果，如适当，将整合到一个新的课程中，突出算法，硬度结果和完整性差距的新兴融合。

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.