TY - GEN

T1 - Constant factor approximation for Balanced Cut in the PIE model

AU - Makarychev, Konstantin

AU - Makarychev, Yury

AU - Vijayaraghavan, Aravindan

N1 - Copyright:
Copyright 2014 Elsevier B.V., All rights reserved.

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Approximation algorithm

KW - Average-case analysis

KW - Balanced cut

KW - Random planted model

KW - Semi-random model

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

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

U2 - 10.1145/2591796.2591841

DO - 10.1145/2591796.2591841

M3 - Conference contribution

AN - SCOPUS:84904333304

SN - 9781450327107

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

SP - 41

EP - 49

BT - STOC 2014 - Proceedings of the 2014 ACM Symposium on Theory of Computing

PB - Association for Computing Machinery

T2 - 4th Annual ACM Symposium on Theory of Computing, STOC 2014

Y2 - 31 May 2014 through 3 June 2014

ER -