Max cut and the smallest eigenvalue
Max cut and the smallest eigenvalue
复制标题
DOI：
10.1145/1536414.1536452
复制
发表时间：
2008-06
期刊：
影响因子：
--
通讯作者：
L. Trevisan
中科院分区：
文献类型：
--
作者：
L. Trevisan
我们描述了一种新的 Max Cut 近似算法。我们的算法运行时间约为 O(n2)，其中 n 是顶点数，并达到 0.531 的近似比。在最优解切割 1-ε 部分边缘的情况下，我们的算法会找到切割 1-4√ε + 8ε-o(1) 部分边缘的解决方案。我们的主要结果是频谱划分的一种变体，它可以在几乎线性的时间内实现。给定一张图，其中最大割最优值是边的 1-ε 部分，我们的谱划分算法会找到一组 S 顶点和 S 的二分 L,R=S-L，使得入射在 S 上的边的至少 1-O(√ε) 部分在 L 中具有一个端点，在 R 中具有一个端点。（这可以看作是 Cheeger 不等式的类比，对于 图的邻接矩阵。）迭代此过程会产生上述近似结果。谱划分的一种不同的、更复杂的变体导致了一种多项式时间算法，该算法在图中切割边的 1/2 + e-Ω(1/ε) 部分，其中最佳值为 1/2 + ε。
We describe a new approximation algorithm for Max Cut. Our algorithm runs in ~O(n2) time, where n is the number of vertices, and achieves an approximation ratio of .531. On instances in which an optimal solution cuts a 1-ε fraction of edges, our algorithm finds a solution that cuts a 1-4√ε + 8ε-o(1) fraction of edges. Our main result is a variant of spectral partitioning, which can be implemented in nearly linear time. Given a graph in which the Max Cut optimum is a 1-ε fraction of edges, our spectral partitioning algorithm finds a set S of vertices and a bipartition L,R=S-L of S such that at least a 1-O(√ε) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analog of Cheeger's inequality for the smallest eigenvalue of the adjacency matrix of a graph.) Iterating this procedure yields the approximation results stated above. A different, more complicated, variant of spectral partitioning leads to a polynomial time algorithm that cuts a 1/2 + e-Ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε.