# Approximation Algorithm for Sparsest k-Partitioning

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jun 2013.

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

- [Provable Guarantees for Self-Supervised Deep Learning with Spectral Contrastive Loss](https://mlsanity.com/paper/2106.04156/) (2021)
- [Beyond Separability: Analyzing the Linear Transferability of Contrastive Representations to Related Subpopulations](https://mlsanity.com/paper/2204.02683/) (2022)
- [Cluster-aware Semi-supervised Learning: Relational Knowledge Distillation Provably Learns Clustering](https://mlsanity.com/paper/2307.11030/) (2023)
- [Weakly-Supervised Contrastive Learning for Imprecise Class Labels](https://mlsanity.com/paper/2505.22028/) (2025)

## Abstract (arXiv)

Given a graph G, the sparsest-cut problem asks to find the set of vertices S which has the least expansion defined as φG(S) := fracw(E(S,barS))min setw(S), w(barS),  where w is the total edge weight of a subset. Here we study the natural generalization of this problem: given an integer k, compute a k-partition setP1, ldots, Pk of the vertex set so as to minimize  φk(setP1, ldots, Pk) := maxi φG(Pi).  Our main result is a polynomial time bi-criteria approximation algorithm which outputs a (1 - e)k-partition of the vertex set such that each piece has expansion at most Ovarepsilon(√log n log k) times OPT. We also study balanced versions of this problem.