TY - GEN

T1 - Approximation algorithms for semi-random partitioning problems

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

PY - 2012/6/26

Y1 - 2012/6/26

N2 - In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real-world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser. We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than most algorithms for previously studied random and semi-random models. Additionally, we study a new planted algebraic expander model and develop constant factor bi-criteria approximation algorithms for graph partitioning problems in this model.

AB - In this paper, we propose and study a new semi-random model for graph partitioning problems. We believe that it captures many properties of real-world instances. The model is more flexible than the semi-random model of Feige and Kilian and planted random model of Bui, Chaudhuri, Leighton and Sipser. We develop a general framework for solving semi-random instances and apply it to several problems of interest. We present constant factor bi-criteria approximation algorithms for semi-random instances of the Balanced Cut, Multicut, Min Uncut, Sparsest Cut and Small Set Expansion problems. We also show how to almost recover the optimal solution if the instance satisfies an additional expanding condition. Our algorithms work in a wider range of parameters than most algorithms for previously studied random and semi-random models. Additionally, we study a new planted algebraic expander model and develop constant factor bi-criteria approximation algorithms for graph partitioning problems in this model.

KW - approximation algorithm

KW - average-case analysis

KW - graph partitioning

KW - random planted model

KW - semi-random model

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

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

U2 - 10.1145/2213977.2214013

DO - 10.1145/2213977.2214013

M3 - Conference contribution

AN - SCOPUS:84862617734

SN - 9781450312455

T3 - Proceedings of the Annual ACM Symposium on Theory of Computing

SP - 367

EP - 384

BT - STOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing

T2 - 44th Annual ACM Symposium on Theory of Computing, STOC '12

Y2 - 19 May 2012 through 22 May 2012

ER -