Speaker Anand Louis
Host Kostya Makarychev
Date recorded 12 February 2013
Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subsetS such that its expansion (a.k.a. conductance ofS or the sparsity of the cut(S,S ̅) ) is bounded as follows:
ϕ(S)=w(S,S ̅ )/(w(S))≤√(2λ2 ),
where w is the total edge weight of a subset or a cut andλ2 is the second smallest eigenvalue of the normalized Laplacian of the graph.
I will talk about some natural generalizations of the sparsest cut in a graph:
I will present some extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian and some approximation-algorithms for them. In particular, for the sparsestk-partition, we prove that the sparsity is at most8√(λk ) log k whereλk is the k-th smallest eigenvalue of the normalized Laplacian matrix. For the k sparse cuts problem we prove that there exist ck disjoint subsetsS1,…,S(1-ε)k, such that
maxiϕ(Si )≤C √λk logk
whereC0 are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for anyk, there is a subsetS whose weight is at most aO(1/k) fraction of the total weight andϕ(S)≤ C √λk logk. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method.
Based on joint works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.
©2013 Microsoft Corporation. All rights reserved.