Max Cut and the Smallest Eigenvalue

Details Max Cut and the Smallest Eigenvalue Max Cut and the Smallest Eigenvalue

2008-06-12

arxiv.org/abs/0806.1978v5

Computer Science

Data Structures and Algorithms

Scientific paper

We describe a new approximation algorithm for Max Cut. Our algorithm runs in $\tilde O(n^2)$ 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-\epsilon$ fraction of edges, our algorithm finds a solution that cuts a $1-4\sqrt{\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(\sqrt \epsilon)$ 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 an $\tilde O(n^3)$ time algorithm that cuts $1/2 + e^{-\Omega(1/\eps)}$ fraction of edges in graphs in which the optimum is $1/2 + \epsilon$.

Affiliated with

Also associated with

No associations

Rating

Max Cut and the Smallest Eigenvalue does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Max Cut and the Smallest Eigenvalue, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Max Cut and the Smallest Eigenvalue will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-689890