CAREER: Approximation and Hardness from Strong Relaxations

Cornell University, Ithaca NY

Investigators

Abstract

Discrete optimization lies at the core of computer science and its applications. Except for a few special cases, exact optimization is computationally intractable. Approximation algorithms seek to resolve this issue by providing computational efficiency and at the same time provable guarantees on the quality of solutions. The current project addresses fundamental open questions about approximation algorithms. The project will use strong relaxations, especially the sum-of-squares method, as a lens to shed light on these questions. The Unique Games Conjecture has fueled many recent advances in our understanding of approximation algorithms. A proof of this conjecture would show that for a large classes of problems the approximation guarantees of a concrete algorithm are best possible. On the other hand, a refutation of the conjecture would likely lead to major improvements of approximation algorithms for a wide range of problems. Recent works of the PI and coauthors identified a candidate algorithm to refute the Unique Games Conjecture. This algorithm is able to solve previously proposed constructions of hard instances for problems that the conjecture predicts to be NP-hard. An integral part of the research project is to resolve whether this algorithm indeed refutes the conjecture. The candidate algorithm comes from a meta-algorithm, called sum-of-squares method. The current project will also study the approximation guarantees of this method beyond the Unique Games Conjecture, and investigate the thesis that for a large class of problems, the sum-of-squares method is an optimal meta-algorithm in terms of approximation guarantee and time complexity. A broad range of academic disciplines apply optimization techniques and computational efficiency is an important factor in these applications. In practice, meta-algorithms are often a popular choice, e.g., belief propagation, MCMC methods and SAT solvers, but lack provable approximation guarantees. The sum-of-squares method has the potential to achieve the same versatility as other meta-algorithms but with the additional benefit of provable guarantees.