  


A Spectral Algorithm for Improving Graph Partitions
Michael W. Mahoney(mahoneymwgmail.com) Abstract: In the cutimprovement problem, we are asked, given a starting cut (T,V\T) in a graph G, to find a cut with low conductance around(T, V\T) or produce a certificate that there is none. More precisely, for a notion of correlation between cuts, cutimprovement algorithms seek to produce approximation guarantees of the following form: for any cut (C, V\C) that is tcorrelated with the input cut, the cut output by the algorithm has conductance upperbounded by a function of the conductance of (C, V\C) and t. In this paper we approach the cutimprovement problem from a spectral perspective: given a graph G and a cut (T,V\T), we first associate a natural unit vector to (T,V\T). Then we modify the standard spectral relaxation for G to bias it towards this vector, and use this relaxation to present a new cutimprovement algorithm, SpImprove. Our relaxation gives rise to a geometric notion of correlation among cuts. Moreover, we show that the classic sweepcut rounding can still be applied and that we can solve our relaxation in nearly linear time by reducing it to an eigenvector computation. Further, we show how our approach is intimately connected to electrical networks in one limiting case. We believe this connection may be of independent interest. Finally, we compare our algorithm to the previous flowbased algorithm of Andersen and Lang. We show that SpImprove is likely to be faster and give better approximation guarantees in many settings. Keywords: Spectral Methods, Graph Partitioning Category 1: Combinatorial Optimization (Approximation Algorithms ) Citation: Download: [PDF] Entry Submitted: 12/03/2009 Modify/Update this entry  
Visitors  Authors  More about us  Links  
Subscribe, Unsubscribe Digest Archive Search, Browse the Repository

Submit Update Policies 
Coordinator's Board Classification Scheme Credits Give us feedback 
Optimization Journals, Sites, Societies  