Improved Cheeger's inequality

DOI10.1145/2488608.2488611zbMath1293.05301arXiv1301.5584OpenAlexW2004879152MaRDI QIDQ5495771

Luca Trevisan, Yin Tat Lee, Tsz Chiu Kwok, Shayan Oveis Gharan, Lap Chi Lau

Publication date: 7 August 2014

Published in: Proceedings of the forty-fifth annual ACM symposium on Theory of Computing (Search for Journal in Brave)

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

zbMATH Keywords

graph partitioningspectral algorithm

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)

Related Items (24)

The diameter of the uniform spanning tree of dense graphs ⋮ Spectral concentration and greedy \(k\)-clustering ⋮ Impact of regularization on spectral clustering ⋮ Cheeger Inequalities for General Edge-Weighted Directed Graphs ⋮ Mean isoperimetry with control on outliers: exact and approximation algorithms ⋮ A note on eigenvalue bounds for non‐compact manifolds ⋮ Unnamed Item ⋮ A generalized Cheeger inequality ⋮ The Geometric Meaning of Curvature: Local and Nonlocal Aspects of Ricci Curvature ⋮ Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian ⋮ Multi-way dual Cheeger constants and spectral bounds of graphs ⋮ Improved Cheeger's Inequality and Analysis of Local Graph Partitioning using Vertex Expansion and Expansion Profile ⋮ On the Structure of Isometrically Embeddable Metric Spaces ⋮ Estimates of eigenvalues of the Laplacian by a reduced number of subsets ⋮ Partitioning Well-Clustered Graphs: Spectral Clustering Works! ⋮ Unnamed Item ⋮ Cheeger constants, structural balance, and spectral clustering analysis for signed graphs ⋮ Generalizing the hypergraph Laplacian via a diffusion process with mediators ⋮ Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks ⋮ Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians ⋮ Hermitian Laplacians and a Cheeger Inequality for the Max-2-Lin Problem ⋮ Convex programming based spectral clustering ⋮ Diffusion operator and spectral analysis for directed hypergraph Laplacian ⋮ Spectral clustering revisited: information hidden in the Fiedler vector

This page was built for publication: Improved Cheeger's inequality