Constant Factor Approximation for Balanced Cut in the PIE model
This work addresses the Balanced Cut problem in theoretical computer science, introducing a more general planted model that could be considered incremental as it builds upon prior planted models.
The authors tackled the Balanced Cut problem by proposing a new semi-random semi-adversarial model called PIE, and they developed an approximation algorithm that finds a balanced cut with cost O(|E_random|) + n polylog(n), achieving a constant factor approximation when |E_random| = Ω(n polylog(n)).
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 \text{polylog}(n)$ in this model. In the regime when $|E_{random}| = Ω(n \text{polylog}(n))$, this is a constant factor approximation with respect to the cost of the planted cut.