CAREER: Approximation and Hardness from Strong Relaxations

离散优化是计算机科学及其应用的核心。除了少数特殊情况外，精确优化在计算上是难以处理的。近似算法寻求通过提供计算效率来解决这个问题，同时对解的质量提供可证明的保证。目前的项目解决了关于近似算法的基本开放问题。该项目将使用强松弛法，特别是平方和法，作为透镜来阐明这些问题。独特博弈猜想推动了我们对近似算法的理解。对这一猜想的证明表明，对于大量的问题，具体算法的近似保证是最好的。另一方面，对这一猜想的反驳可能会导致对广泛问题的近似算法的重大改进。PI和合作者最近的工作确定了一个候选算法来反驳唯一游戏猜想。该算法能够解决先前提出的关于猜想预测为np困难的问题的硬实例结构。研究项目的一个组成部分是解决这个算法是否确实反驳了这个猜想。候选算法来自一种叫做平方和的元算法。目前的项目还将研究该方法在唯一对策猜想之外的近似保证，并研究对于一大类问题，平方和方法在近似保证和时间复杂度方面是一种最优的元算法。广泛的学科应用优化技术，计算效率是这些应用中的一个重要因素。在实践中，元算法通常是一种流行的选择，例如信念传播、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.