Multi-way spectral partitioning and higher-order cheeger inequalities
Publication:5415539
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
Cheeger's inequality; spectral algorithms; spectral clustering; sparsest cut; Cheeger inequalities; spectral partitioning; random partitions of metric spaces
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)