An optimal sdp algorithm for max-cut, and equally optimal long code tests
An optimal sdp algorithm for max-cut, and equally optimal long code tests
复制标题
用于最大切割的最佳 sdp 算法，以及同样最佳的长代码测试
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Yi Wu
中科院分区：
文献类型：
--
作者：
R. O'Donnell;Yi Wu
令G为一个无方向的图表，标准最大切割SDP松弛至少达到总边缘重量的一小部分，1/2≤c≤1。边缘重量，我们说（C，S）是SDP间隙。 （C，S）是本文中的SDP差距。 c）= s（c）对于特定的显式（但对状态复杂）。特别是，我们的下限gapsdp（c） - s（c）是通过多项式时间-RPR2'算法证明的给定有效的，最佳的SDP旋转算法，以确认是RPR2的事实。在[25，3，4]中，我们使用此连接进行了最佳的长代码测试，以结合[27，29]中的结果，我们得出以下结论： s（c）也给出了最大切割的SDP间隙曲线由于在表现出C和S（C）SDP间隙的图中，我们的RPR2算法实际上找到了最佳切割。以及独特的游戏猜想。
Let G be an undirected graph for which the standard Max-Cut SDP relaxation achieves at least a c fraction of the total edge weight, 1/2 ≤ c ≤ 1. If the actual optimal cut for G is at most an s fraction of the total edge weight, we say that (c, s) is an SDP gap. We define the SDP gap curve GapSDP : [1/2,1] -> [1/2,1] by GapSDP(c) = inf{s : (c, s) is an SDP gap}. In this paper we complete a long line of work [15, 14, 20, 36, 19, 17, 13, 28] by determining the entire SDP gap curve; we show GapSDP(c) = S(c) for a certain explicit (but complicated to state) function S. In particular, our lower bound GapSDP(c) - S(c) is proved via a polynomial-time - RPR2' algorithm. Thus we have given an efficient, optimal SDP-rounding algorithm for Max-Cut. The fact that it is RPR2 confirms a conjecture of Feige and Langberg [17]. We also describe and analyze the tight connection between SDP gaps and Long Code tests (and the constructions of [25, 3, 4]). Using this connection, we give optimal Long Code tests for Max-Cut. Combining these with results implicit in [27, 29] and ideas from [19], we derive the following conclusions: - The Max-Cut SDP gap curve subject to triangle inequalities is also given by S(c). - No RPR2 algorithm can be guaranteed to find cuts of value larger than S(c) in graphs where the optimal cut is c. (Contrast this with the fact that in the graphs exhibiting the c vs. S(c) SDP gap, our RPR2 algorithm actually finds the optimal cut.) - Further, no polynomial-time algorithm of any kind can have such a guarantee, assuming P ≠ NP and the Unique Games Conjecture.