CAREER: Approximation and Hardness from Strong Relaxations

离散优化是计算机科学及其应用的核心。除了少数特殊情况外，精确的最优化在计算上是困难的。近似算法试图通过提供计算效率，同时对解的质量提供可证明的保证来解决这一问题。当前的项目解决了关于近似算法的基本开放问题。该项目将使用强松弛，特别是平方和方法作为镜头来阐明这些问题。独特的游戏猜想推动了我们对近似算法的理解的许多最近的进步。这一猜想的证明将表明，对于一大类问题，一个具体算法的近似保证是最可能的。另一方面，对猜想的反驳可能会导致对广泛问题的近似算法的重大改进。PI和合著者最近的工作确定了一个候选算法来驳斥唯一的游戏猜想。对于猜想预测为NP难的问题，该算法能够解决以前提出的构造难实例的问题。研究项目的一个组成部分是解决该算法是否真的驳斥了猜想。候选算法来自一种称为平方和法的元算法。本项目还将研究这种方法的逼近保证，超越了唯一的Games猜想，并研究了对于一大类问题，平方和方法在逼近保证和时间复杂性方面是一种最优的元算法，广泛的学术学科应用了优化技术，计算效率是这些应用的重要因素。在实践中，元算法往往是一种流行的选择，如信任传播、MCMC方法和SAT求解器，但缺乏可证明的逼近保证。平方和方法有可能实现与其他元算法相同的通用性，但具有可证明的保证的额外好处。

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.