MAX CUT AND THE SMALLEST EIGENVALUE
MAX CUT AND THE SMALLEST EIGENVALUE
复制标题
DOI：
10.1137/090773714
复制
发表时间：
2012-01-01
影响因子：
1.6
通讯作者：
Trevisan, Luca
中科院分区：
文献类型：
--
作者：
Trevisan, Luca
我们描述了一个新的近似算法的最大切割。我们的算法在（O）次内运行（n（2））次，其中n是顶点数，并实现了0.531的近似比。在最优解切割1 - 1/2分数的边的情况下，我们的算法找到切割1-4根1/2 + 8 epsilon-o（1）分数的边的解决方案。我们的主要结果是一个变种的频谱分割，它可以在近线性时间内实现。给定一个图，其中最大割最优是边的1 - 1/2分数，我们的谱划分算法找到一个顶点集S和S的二分划L，R = S-L，使得至少1 - O（根切）分数的边入射到S上，有一个端点在L和一个端点在R。(This可以看作是一个类似的Cheeger不等式的最小特征值的邻接矩阵的图。迭代此过程产生上述近似结果。一个不同的，更复杂的谱划分的变体导致了一个多项式时间算法，它在图中切割1/2 + e（-Omega（1/n））分数的边，其中最佳值是1/2 + e。
We describe a new approximation algorithm for Max Cut. Our algorithm runs in (O) over tilde (n(2)) time, where n is the number of vertices, and achieves an approximation ratio of .531. In instances in which an optimal solution cuts a 1 - epsilon fraction of edges, our algorithm finds a solution that cuts a 1-4 root epsilon + 8 epsilon-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 - epsilon 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(root epsilon) fraction of the edges incident on S have one endpoint in L and one endpoint in R. (This can be seen as an analogue 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(-Omega(1/epsilon)) fraction of edges in graphs in which the optimum is 1/2 + epsilon.