2013/01/23 by Tsz Chiu Kwok, Lap Chi Lau, Kwok, Tsz Chiu +8 · 5 citations
Chemistry · Computer Science · Engineering · Mathematics · #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph theory and applications #Machine Learning (stat.ML) #Metal-Organic Frameworks: Synthesis and Applications #Remote-Sensing Image Classification #Sparse and Compressive Sensing Techniques #Spectral Theory (math.SP) #cs.DM #cs.DS #math.CO #math.SP #stat.ML
paper · pdf · doi:10.48550/arxiv.1301.5584
arxiv created 2013/01/23 · openalex publication_date 2013/01/23 · arxiv updated 2013/01/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let ϕ(G) be the minimum conductance of an undirected graph G, and let 0=λ1 <= λ2 <=... <= λn <= 2 be the eigenvalues of the normalized Laplacian matrix of G. We prove that for any graph G and any k >= 2, ϕ(G) = O(k) λ2 / √(λk), and this performance guarantee is achieved by the spectral partitioning algorithm. This improves Cheeger's inequality, and the bound is optimal up to a constant factor for any k. Our result shows that the spectral partitioning algorithm is a constant factor approximation algorithm for finding a sparse cut if λk is a constant for some constant k. This provides some theoretical justification to its empirical performance in image segmentation and clustering problems. We extend the analysis to other graph partitioning problems, including multi-way partition, balanced separator, and maximum cut.