Approximation algorithms for semi-random partitioning problems

Konstantin Makarychev*, Yury Makarychev, Aravindan Vijayaraghavan

*Corresponding author for this work

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

31 Scopus citations

Abstract

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.

Original languageEnglish (US)
Title of host publicationSTOC '12 - Proceedings of the 2012 ACM Symposium on Theory of Computing
Pages367-384
Number of pages18
DOIs
StatePublished - Jun 26 2012
Event44th Annual ACM Symposium on Theory of Computing, STOC '12 - New York, NY, United States
Duration: May 19 2012May 22 2012

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Other

Other44th Annual ACM Symposium on Theory of Computing, STOC '12
CountryUnited States
CityNew York, NY
Period5/19/125/22/12

Keywords

  • approximation algorithm
  • average-case analysis
  • graph partitioning
  • random planted model
  • semi-random model

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Approximation algorithms for semi-random partitioning problems'. Together they form a unique fingerprint.

Cite this