-

 

 

 




Optimization Online





 

A Spectral Algorithm for Improving Graph Partitions

Michael W. Mahoney(mahoneymw***at***gmail.com)
Lorenzo Orecchia(orecchia***at***eecs.berkeley.edu)
Nisheeth K. Vishnoi(nisheeth.vishnoi***at***gmail.com)

Abstract: In the cut-improvement 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, cut-improvement algorithms seek to produce approximation guarantees of the following form: for any cut (C, V\C) that is t-correlated with the input cut, the cut output by the algorithm has conductance upper-bounded by a function of the conductance of (C, V\C) and t. In this paper we approach the cut-improvement 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 cut-improvement algorithm, SpImprove. Our relaxation gives rise to a geometric notion of correlation among cuts. Moreover, we show that the classic sweep-cut 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 flow-based 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
Entry Accepted: 12/03/2009
Entry Last Modified: 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
Mathematical Programming Society