# On Uniform Capacitated k-Median Beyond the Natural LP Relaxation

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Sep 2014.

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

- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)
- [A Polynomial-Time Approximation for Pairwise Fair k-Median Clustering](https://mlsanity.com/paper/2405.10378/) (2024)
- [Welfare-Centric Clustering](https://mlsanity.com/paper/2508.10345/) (2025)

## Abstract (arXiv)

In this paper, we study the uniform capacitated k-median problem. Obtaining a constant approximation algorithm for this problem is a notorious open problem; most previous works gave constant approximations by either violating the capacity constraints or the cardinality constraint. Notably, all these algorithms are based on the natural LP-relaxation for the problem. The LP-relaxation has unbounded integrality gap, even when we are allowed to violate the capacity constraints or the cardinality constraint by a factor of 2-ε. Our result is an exp(O(1/ε2))-approximation algorithm for the problem that violates the cardinality constraint by a factor of 1+ε. This is already beyond the capability of the natural LP relaxation, as it has unbounded integrality gap even if we are allowed to open (2-ε)k facilities. Indeed, our result is based on a novel LP for this problem. The version as we described is the hard-capacitated version of the problem, as we can only open one facility at each location. This is as opposed to the soft-capacitated version, in which we are allowed to open more than one facilities at each location. We give a simple proof that in the uniform capacitated case, the soft-capacitated version and the hard-capacitated version are actually equivalent, up to a small constant loss in the approximation ratio.