Multi-way spectral partitioning and higher-order cheeger inequalities

DOI10.1145/2213977.2214078zbMath1286.05091arXiv1111.1055MaRDI QIDQ5415539

Luca Trevisan, Shayan Oveis Gharan, James R. Lee

Publication date: 13 May 2014

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

Full work available at URL: https://arxiv.org/abs/1111.1055

zbMATH Keywords

Cheeger's inequality; spectral algorithms; spectral clustering; sparsest cut; Cheeger inequalities; spectral partitioning; random partitions of metric spaces

Mathematics Subject Classification ID

60C05: Combinatorial probability

05C50: Graphs and linear algebra (matrices, eigenvalues, etc.)

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

05C85: Graph algorithms (graph-theoretic aspects)