Constant factor approximation for balanced cut in the PIE model

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