Max Cut and the Smallest Eigenvalue
| dc.creator | Trevisan, Luca | |
| dc.date | 2008-06-12 | |
| dc.date | 2008-12-08 | |
| dc.date.accessioned | 2026-07-07T12:09:40Z | |
| dc.date.available | 2026-07-07T12:09:40Z | |
| dc.description | 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-ε$ fraction of edges, our algorithm finds a solution that cuts a $1-4\sqrtε + 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(\sqrt ε)$ 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^{-Ω(1/\eps)}$ fraction of edges in graphs in which the optimum is $1/2 + ε$. | |
| dc.identifier | https://arxiv.org/abs/0806.1978 | |
| dc.identifier | http://arxiv.org/abs/0806.1978 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/209701 | |
| dc.subject | Data Structures and Algorithms | |
| dc.title | Max Cut and the Smallest Eigenvalue | |
| dc.type | text |