# Constant Factor Approximation for Balanced Cut in the PIE model

arXiv: https://arxiv.org/abs/1406.5665 · HTML: https://mlsanity.com/paper/1406.5665/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 22 Jun 2014.

## Built on by (most cited first, 3 of 3)

- [Semi-Random Sparse Recovery in Nearly-Linear Time](https://mlsanity.com/paper/2203.04002/) (2022)
- [A Near-Linear Time Approximation Algorithm for Beyond-Worst-Case Graph Clustering](https://mlsanity.com/paper/2406.04857/) (2024)
- [A Sublinear-Time Spectral Clustering Oracle with Improved Preprocessing Time](https://mlsanity.com/paper/2310.17878/) (2023)

## Abstract (arXiv)

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 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| = Omega(n polylog(n)), this is a constant factor approximation with respect to the cost of the planted cut.