Constant factor approximation for Balanced Cut in the PIE model

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

14 Scopus citations

Abstract

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutationinvariant random edges (PIE). Our model is much more general than planted models considered previously. Consider a set of vertices V partitioned into two clusters L and R of equal size. Let G be an arbitrary graph on V with no edges between L and R. Let Erandom be a set of edges sampled from an arbitrary permutation-invariant distribution (a distribution that is invariant under permutation of vertices in L and in R). Then we say that G+Erandom is a graph with permutation-invariant random edges. We present an approximation algorithm for the Balanced Cut problem that finds a balanced cut of cost O(|Erandom|)+n polylog(n) in this model. In the regime when |Erandom| = Ω(n polylog(n)), this is a constant factor approximation with respect to the cost of the planted cut.

Original languageEnglish (US)
Title of host publicationSTOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing
PublisherAssociation for Computing Machinery
Pages41-49
Number of pages9
ISBN (Print)9781450327107
DOIs
StatePublished - 2014
Event4th Annual ACM Symposium on Theory of Computing, STOC 2014 - New York, NY, United States
Duration: May 31 2014Jun 3 2014

Publication series

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

Other

Other4th Annual ACM Symposium on Theory of Computing, STOC 2014
CountryUnited States
CityNew York, NY
Period5/31/146/3/14

Keywords

  • Approximation algorithm
  • Average-case analysis
  • Balanced cut
  • Random planted model
  • Semi-random model

ASJC Scopus subject areas

  • Software

Fingerprint Dive into the research topics of 'Constant factor approximation for Balanced Cut in the PIE model'. Together they form a unique fingerprint.

Cite this