Approximation algorithm for sparsest k-partitioning

Anand Louis; Konstantin Makarychev

doi:10.1137/1.9781611973402.92

Approximation algorithm for sparsest k-partitioning

Anand Louis^*, Konstantin Makarychev

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

18 Scopus citations

Abstract

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 {P₁...., P_k} of the vertex set so as to minimize φ^k_G({P ₁,...,P_k})=def max I φ_G(P_i). 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 language	English (US)
Title of host publication	Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Publisher	Association for Computing Machinery
Pages	1244-1255
Number of pages	12
ISBN (Print)	9781611973389
DOIs	https://doi.org/10.1137/1.9781611973402.92
State	Published - 2014
Event	25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 - Portland, OR, United States Duration: Jan 5 2014 → Jan 7 2014

Publication series

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

Other

Other	25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014
Country/Territory	United States
City	Portland, OR
Period	1/5/14 → 1/7/14

ASJC Scopus subject areas

Software
General Mathematics

Access to Document

10.1137/1.9781611973402.92

Cite this

@inproceedings{67b12c08e6ce4005b5b098afa0fd3e4d,

title = "Approximation algorithm for sparsest k-partitioning",

abstract = "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.",

author = "Anand Louis and Konstantin Makarychev",

year = "2014",

doi = "10.1137/1.9781611973402.92",

language = "English (US)",

isbn = "9781611973389",

series = "Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms",

publisher = "Association for Computing Machinery",

pages = "1244--1255",

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

note = "25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014 ; Conference date: 05-01-2014 Through 07-01-2014",

}

Louis, A & Makarychev, K 2014, Approximation algorithm for sparsest k-partitioning. in Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, pp. 1244-1255, 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, OR, United States, 1/5/14. https://doi.org/10.1137/1.9781611973402.92

Approximation algorithm for sparsest k-partitioning. / Louis, Anand; Makarychev, Konstantin.
Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014. Association for Computing Machinery, 2014. p. 1244-1255 (Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 -

Approximation algorithm for sparsest k-partitioning

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this