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

Carnegie Mellon University, Pittsburgh PA

Investigators

Abstract

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.