Approximation algorithm for sparsest k-partitioning

Anand Louis*, Konstantin Makarychev

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference contribution

12 Scopus citations


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.

Original languageEnglish (US)
Title of host publicationProceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
PublisherAssociation for Computing Machinery
Number of pages12
ISBN (Print)9781611973389
StatePublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States
Duration: Jan 5 2014Jan 7 2014

Publication series

NameProceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms


Other25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
CountryUnited States
CityPortland, OR

ASJC Scopus subject areas

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'Approximation algorithm for sparsest k-partitioning'. Together they form a unique fingerprint.

Cite this