0(\sqrt {\log n)} Approximation to SPARSEST CUT in Õ(n²) Time

Authors:

Abstract
We show how to compute O(/spl radic/log n)-approximations to SPARSEST CUT and BALANCED SEPARATOR problems in O/spl tilde/(n/sup 2/) time, thus improving upon the recent algorithm of Arora, Rao and Vazirani (2004). Their algorithm uses semidefinite programming and required O/spl tilde/(n/sup 4.5/) time. Our algorithm relies on efficiently finding expander flows in the graph and does not solve semidefinite programs. The existence of expander flows was also established by Arora, Rao, and Vazirani.

This publication has 17 references indexed in Scilit: