Constant Factor Approximation for Balanced Cut in the PIE Model

We propose and study a new semi-random semi-adversarial model for Balanced Cut, a planted model with permutation-invariant 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 E_random 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 + E_random 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(|E_random|) + n polylog(n) in this model.

Joint work with: Konstantin Makarychev and Aravindan Vijayaraghavan