Max cut and the smallest eigenvalue

DOI10.1145/1536414.1536452zbMath1304.05140OpenAlexW2109154425MaRDI QIDQ5172720

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

Analysis of algorithms and problem complexity (68Q25) 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) Approximation algorithms (68W25)

Related Items (9)

Purely combinatorial approximation algorithms for maximum \(k\)-vertex cover in bipartite graphs ⋮ Combinatorial approximation of maximum k-vertex cover in bipartite graphs within ratio 0.7 ⋮ Logit dynamics with concurrent updates for local interaction potential games ⋮ Minimizing the least eigenvalue of graphs with fixed order and size ⋮ Anti-modularity and anti-community detecting in complex networks ⋮ Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians ⋮ Convex Relaxations and Integrality Gaps ⋮ The spectral radius of irregular graphs ⋮ On a Cheeger type inequality in Cayley graphs of finite groups

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