How to Round Any CSP
How to Round Any CSP
复制标题
如何舍入任何 CSP
DOI：
10.1109/focs.2009.74
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
David Steurer
中科院分区：
文献类型：
--
作者：
P. Raghavendra;David Steurer
Max Cut，Max K-SAT和独特游戏等大量有趣的组合优化问题属于约束满意度问题（CSP）。其中一位作者的最新工作（Stoc 2008）确定了在独特的游戏猜想（UGC）下，半决赛编程（SDP）放松得出每个CSP的最佳近似值。最近（FOCS 2009），作者还无条件地表明，无法通过添加大量有效的不平等（例如，以Sherali-Adams LP层次结构）来减少这种基本SDP松弛的完整性差距。在这项工作中，我们提出了一个有效的舍入方案，该方案实现了每个CSP基本SDP松弛的完整性差距（并且还达到了更强的SDP松弛的差距）。我们认为的SDP放松更强或等同于文献中用于近似CSP的任何放松。因此，不论教资会的真相如何，我们的工作都产生了一种有效的通用算法，对于每个CSP，至少与最著名的文学算法一样好。本文中的四舍五入算法可以简洁地概括如下：通过随机投影，离散投影向量并通过蛮力解决所得的CSP实例！甚至证明也很简单，因为它可以避免使用独特游戏减少的机械，例如独裁统治测试，傅立叶分析或不变性原理。本文的一个共同主题和同一会议中的后续论文是SDP松弛的鲁棒性引理，它断言，可以通过“平滑”而无需显着更改客观价值来使大约可行的解决方案可行。
A large number of interesting combinatorial optimization problems like MAX CUT, MAX k-SAT, and UNIQUE GAMES fall under the class of constraint satisfaction problems (CSPs). Recent work by one of the authors (STOC 2008) identifies a semidefinite programming (SDP) relaxation that yields the optimal approximation ratio for every CSP, under the Unique Games Conjecture (UGC). Very recently (FOCS 2009), the authors also showed unconditionally that the integrality gap of this basic SDP relaxation cannot be reduced by adding large classes of valid inequalities (e.g., in the fashion of Sherali--Adams LP hierarchies). In this work, we present an efficient rounding scheme that achieves the integrality gap of this basic SDP relaxation for every CSP (and it also achieves the gap of much stronger SDP relaxations). The SDP relaxation we consider is stronger or equivalent to any relaxation used in literature to approximate CSPs. Thus, irrespective of the truth of the UGC, our work yields an efficient generic algorithm that for every CSP, achieves an approximation at least as good as the best known algorithm in literature. The rounding algorithm in this paper can be summarized succinctly as follows: Reduce the dimension of SDP solution by random projection, discretize the projected vectors, and solve the resulting CSP instance by brute force! Even the proof is simple in that it avoids the use of the machinery from unique games reductions such as dictatorship tests, Fourier analysis or the invariance principle. A common theme of this paper and the subsequent paper in the same conference is a robustness lemma for SDP relaxations which asserts that approximately feasible solutions can be made feasible by "smoothing'' without changing the objective value significantly.