Loading...
Please wait, while we are loading the content...
Similar Documents
Max Cut and the Smallest Eigenvalue (2008)
| Content Provider | CiteSeerX |
|---|---|
| Author | Trevisan, Luca |
| Abstract | We describe a new approximation algorithm for Max Cut. Our algorithm runs in Õ(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 an Õ(n3) time algorithm that cuts 1/2 + e −Ω(1/ε) fraction of edges in graphs in which the optimum is 1/2 + ε. 1 |
| File Format | |
| Publisher Date | 2008-01-01 |
| Access Restriction | Open |
| Subject Keyword | Approximation Ratio Spectral Partitioning New Approximation Algorithm Max Cut Smallest Eigenvalue Linear Time Approximation Result Spectral Partitioning Algorithm Optimal Solution Adjacency Matrix Max Cut Optimum |
| Content Type | Text |
