TY - GEN
T1 - Constant factor approximation for Balanced Cut in the PIE model
AU - Makarychev, Konstantin
AU - Makarychev, Yury
AU - Vijayaraghavan, Aravindan
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 -