Algorithmic Extensions of Cheeger’s Inequality to Higher Eigenvalues and Partitions

DOI10.1007/978-3-642-22935-0_27zbMath1321.05152OpenAlexW1576252999MaRDI QIDQ3088104

Prasad Raghavendra, Anand Louis, Santosh Vempala, Prasad Tetali

Publication date: 17 August 2011

Published in: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-22935-0_27

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)

Related Items

Clustering and outlier detection using isoperimetric number of trees, Multi-way spectral partitioning and higher-order cheeger inequalities, Generalizing the hypergraph Laplacian via a diffusion process with mediators, Diffusion operator and spectral analysis for directed hypergraph Laplacian

Cites Work

• \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
• Eigenvalues and expanders
• Approximations for the isoperimetric and spectral profile of graphs and related parameters
• Graph expansion and the unique games conjecture
• Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms
• Subexponential Algorithms for Unique Games and Related Problems
• Geometric bounds on the Ornstein-Uhlenbeck velocity process
• On clusterings
• Breaking the multicommodity flow barrier for o(√log n)-approximations to sparsest cut
• Graph partitioning using single commodity flows
• Expander flows, geometric embeddings and graph partitioning