
Speaker Anand Louis Host Kostya Makarychev Duration 00:54:04 Date recorded 12 February 2013 Cheeger's fundamental inequality states that any edgeweighted 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 approximationalgorithms for them. In particular, for the sparsestkpartition, we prove that the sparsity is at most8√(λ_{k} ) log k whereλk is the kth 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ϕ(S_{i} )≤C √λ_{k} logk whereC0 are suitable absolute constants; this leads to a similar bound for the smallset 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.
