Review paper
Max Cut and the Smallest Eigenvalue
Abstract
We describe a new approximation algorithm for Max Cut. Our algorithm runs in \tilde O(n^2)time, where nis the number of vertices, and achieves an approximation ratio of .531 In instances in which an optimal solution cuts a 1-\varepsilonfraction of edges, our algorithm finds a solution that cuts a 1-4\sqrt{\varepsilon} + 8\varepsilon-o(1)fraction of edges. Our main result is a variant of spectral partitioning, which can be...
Paper Details
Title
Max Cut and the Smallest Eigenvalue
Published Date
Jan 1, 2012
Journal
Volume
41
Issue
6
Pages
1769 - 1786
Citation AnalysisPro
You’ll need to upgrade your plan to Pro
Looking to understand the true influence of a researcher’s work across journals & affiliations?
- Scinapse’s Top 10 Citation Journals & Affiliations graph reveals the quality and authenticity of citations received by a paper.
- Discover whether citations have been inflated due to self-citations, or if citations include institutional bias.
Notes
History