# K-median: exact recovery in the extended stochastic ball model

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Sep 2021.

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

- [Local versions of sum-of-norms clustering](https://mlsanity.com/paper/2109.09589/) (2021)
- [BalLOT: Balanced k-means clustering with optimal transport](https://mlsanity.com/paper/2512.05926/) (2025)

## Abstract (arXiv)

We study exact recovery conditions for the linear programming relaxation of the k-median problem in the stochastic ball model (SBM). In Awasthi et al. (2015), the authors give a tight result for the k-median LP in the SBM, saying that exact recovery can be achieved as long as the balls are pairwise disjoint. We give a counterexample to their result, thereby showing that the k-median LP is not tight in low dimension. Instead, we give a near optimal result showing that the k-median LP in the SBM is tight in high dimension. We also show that, if the probability measure satisfies some concentration assumptions, then the k-median LP in the SBM is tight in every dimension. Furthermore, we propose a new model of data called extended stochastic ball model (ESBM), which significantly generalizes the well-known SBM. We then show that exact recovery can still be achieved in the ESBM.