Breaking the Multicommodity Flow Barrier for ?log(n)-Approximations to Sparsest Cut

June 9, 2010
Jonah Sherman | UC Berkeley

We present an algorithm for the sparsest cut problem that simultaneously achieves the better approximation factor of SDP/multicommodity-flow based algorithms and the subquadratic running time of single-commodity flow based algorithms. The idea is that we can turn Arora, Rao, and Vazirani’s matching-chaining argument into an algorithm for finding good augmenting paths in a multicommodity flow network. Our analysis follows ARV’s, making essential use of measure concentration on the sphere.

Speaker Details

Jonah Sherman is a 3rd year PhD student at the UC Berkeley CS Dept. His main interests are in graph cut/flow algorithms, SDPs, and unique games. Jonah is a Microsoft Fellow and currently intern with the Theory group. He received the FOCS 2009 Best Student Paper Award for the work he will present in this talk.