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 -