AF: Small: Some Frontiers in the Approximability of Constraint Satisfaction and Related Problems

许多重要的计算任务可以归结为优化问题，其目标是找到一个满足规定约束的解，使某个目标值最大化或最小化。不幸的是，这些问题中的大多数都是NP-困难的，难以以最优方式解决。解决这一难题的最广泛研究和最成功的方法之一是采用近似算法，这是一种高效的启发式算法，可以找到具有可证明质量保证的解决方案。这种方法很有吸引力，因为它不会对问题实例做出任何假设。此外，在典型情况下，该算法可以比已证明的界执行得更好。这一课题的研究已经取得了长足的进步，对于许多问题，我们现在已经有了很好的逼近算法以及很强的互补硬度结果。事实上，对于较大类别的问题，一个共同的前沿被认为是已知技术所能达到的最佳逼近。尽管取得了所有这些进展，但某些类别的优化问题一直未能解决现有的技术，它们的地位仍然悬而未决。此外，最近的突破开启了令人兴奋的研究课题，这是以前无法想象的。拟议的研究将查明和调查在基本技术和最终结果说明方面缺乏进展的几个此类前沿领域。所研究的主题将包括强半定规划松弛在解决一些困难的优化问题时的算法能力，寻求满足全局性质的解的约束满足风格问题，以及约束满足问题的(近)可满足实例的逼近性。对探索性主题的初步调查，如与参数化复杂性的联系，以及在一些已知结果中绕过唯一的游戏猜想的可能性。拟议的研究将阐明抽象实践中一些核心计算任务的基本优化问题的可逼近性。研究和外联活动将旨在促进近似和约束满足社区之间的思想交流，这两个社区在很大程度上是通过不同的方法取得进展，几乎没有互动。在教育方面，该项目将培训和指导研究生，并为他们提供一个鼓舞人心的研究环境。研究结果将适当地整合到一门统一的课程中，突出逼近算法和不可逼近结果的新兴融合。

Many important computational tasks can be cast as optimization problems, where the goal is to find a solution obeying stipulated constraints that maximizes or minimizes a certain objective value. Unfortunately, most of these problems are NP-hard to solve optimally. One of the most extensively studied and successful approaches to cope with this intractability is to settle for approximation algorithms, which are efficient heuristics that find solutions with provable guarantees on quality. This approach is appealing as it does not make any assumptions about the problem instance. Further, on typical instances the algorithm could perform much better than the proven bound. Research in this subject has made huge strides, and for many problems we now have good approximation algorithms as well as strong complementary hardness results. In fact, for large classes of problems, a common frontier called ``Unique-Games hardness'' has been identified as the best approximation achievable with known techniques.Despite all this progress, certain classes of optimization problems have eluded existing techniques and their status remains wide open. Also, the recent breakthroughs open up exciting research topics that could not be imagined before. The proposed research will identify and investigate several such frontiers where progress has been lacking, both in terms of the underlying techniques as well as the end result statements. The topics studied will include the algorithmic power of strong semidefinite programming relaxations to tackle some difficult optimization problems, constraint satisfaction style problems where a solution obeying a global property is sought, and the approximability of (near)-satisfiable instances of constraint satisfaction problems. Initial investigations into exploratory topics such as connections with parameterized complexity and the possibility of bypassing the Unique Games conjecture in some of its known consequences will also be pursued.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, which have largely progressed via disparate methods with little interaction. On the education front, the project will train and mentor graduate students and provide a stimulating research environment for them. The research findings, as appropriate, will be integrated into a unified course highlighting the emerging confluence of approximation algorithms and inapproximability results.