TY - GEN

T1 - Approximation algorithm for sparsest k-partitioning

AU - Louis, Anand

AU - Makarychev, Konstantin

PY - 2014

Y1 - 2014

N2 - Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as , φG(S) =def w(E(S,S̄)) /min{w(S), w(S̄)} where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k-partition {P1...., Pk} of the vertex set so as to minimize φkG({P 1,...,Pk})=def max I φG(Pi). Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 - ε)k-partition of the vertex set such that each piece has expansion at most Oε (√log n log k) times OPT. We also study balanced versions of this problem.

AB - Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as , φG(S) =def w(E(S,S̄)) /min{w(S), w(S̄)} where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k-partition {P1...., Pk} of the vertex set so as to minimize φkG({P 1,...,Pk})=def max I φG(Pi). Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 - ε)k-partition of the vertex set such that each piece has expansion at most Oε (√log n log k) times OPT. We also study balanced versions of this problem.

UR - http://www.scopus.com/inward/record.url?scp=84902097281&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902097281&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.92

DO - 10.1137/1.9781611973402.92

M3 - Conference contribution

AN - SCOPUS:84902097281

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 1244

EP - 1255

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -