Max CUT and the smallest eigenvalue

DOI10.1145/1536414.1536452MaRDI QIDQ5172720zbMATH OpenOpenAlexFDO

Authors Luca Trevisan

Publication date 4 February 2015

Published in Proceedings of the forty-first annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/1536414.1536452

zbMATH Keywords

maximum cutspectral partitioning

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Recommendations

• Max cut and the smallest eigenvalue
• Improved Analysis of a Max-Cut Algorithm Based on Spectral Partitioning
• scientific article; zbMATH DE number 1787231
• A spectral partitioning algorithm for maximum directed cut problem
• Bipartite Subgraphs and the Smallest Eigenvalue

Cited in

(19)

• The spectral radius of irregular graphs
• Laplacian eigenvalues and the maximum cut problem
• Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs
• On a Cheeger type inequality in Cayley graphs of finite groups
• A max-cut approximation using a graph based MBO scheme
• Convex relaxations and integrality gaps
• Minimizing the least eigenvalue of graphs with fixed order and size
• Combinatorial approximation of maximum \(k\)-vertex cover in bipartite graphs within ratio 0,7
• Max cut and the smallest eigenvalue
• Bipartite Subgraphs and the Smallest Eigenvalue
• Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem
• Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
• An experimental evaluation of semidefinite programming and spectral algorithms for max cut
• Cheeger's inequalities for vertex expansion and reweighted eigenvalues
• On the nontrivial extremal eigenvalues of graphs
• Worst-case to expander-case reductions: derandomized and generalized
• Anti-modularity and anti-community detecting in complex networks
• Decremental (1+)-approximate maximum eigenvector: dynamic power method
• Logit dynamics with concurrent updates for local interaction potential games

This page was built for publication: Max CUT and the smallest eigenvalue

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5172720)