# New Approximability Results for the Robust k-Median Problem

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

## Key facts

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

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

- [Improved Approximation Algorithms for Individually Fair Clustering](https://mlsanity.com/paper/2106.14043/) (2021)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [Approximating Fair Clustering with Cascaded Norm Objectives](https://mlsanity.com/paper/2111.04804/) (2021)
- [Constant-Factor Approximation Algorithms for Socially Fair k-Clustering](https://mlsanity.com/paper/2206.11210/) (2022)
- [Parameterized Approximation Schemes for Clustering with General Norm Objectives](https://mlsanity.com/paper/2304.03146/) (2023)
- [Parameterized Approximation for Robust Clustering in Discrete Geometric Spaces](https://mlsanity.com/paper/2305.07316/) (2023)

## Abstract (arXiv)

We consider a robust variant of the classical k-median problem, introduced by Anthony et al. citeAnthonyGGN10. In the Robust k-Median problem, we are given an n-vertex metric space (V,d) and m client sets setSi subseteq Vi=1m. The objective is to open a set F subseteq V of k facilities such that the worst case connection cost over all client sets is minimized; in other words, minimize maxi sumv ∈ Si d(F,v). Anthony et al. showed an O(log m) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing Omega(log m/ log log m) approximation hardness, unless sf NP subseteq bigcapδ >0 sf DTIME(2^nδ). This hardness result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances.