# Hardness of Approximation of Euclidean k-Median

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Nov 2020.

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

- [Near-Optimal Explainable k-Means for All Dimensions](https://mlsanity.com/paper/2106.15566/) (2021)
- [Near-optimal Algorithms for Explainable k-Medians and k-Means](https://mlsanity.com/paper/2107.00798/) (2021)
- [Johnson Coverage Hypothesis: Inapproximability of k-means and k-median in L_p metrics](https://mlsanity.com/paper/2111.10912/) (2021)
- [Towards the mathematical foundation of the minimum enclosing ball and related problems](https://mlsanity.com/paper/2402.06629/) (2024)
- [MAC Advice for Facility Location Mechanism Design](https://mlsanity.com/paper/2403.12181/) (2024)

## Abstract (arXiv)

The Euclidean k-median problem is defined in the following manner: given a set X of n points in ℝd, and an integer k, find a set C subset ℝd of k points (called centers) such that the cost function Phi(C,X) equiv sumx ∈ X minc ∈ C |x-c|2 is minimized. The Euclidean k-means problem is defined similarly by replacing the distance with squared distance in the cost function. Various hardness of approximation results are known for the Euclidean k-means problem. However, no hardness of approximation results were known for the Euclidean k-median problem. In this work, assuming the unique games conjecture (UGC), we provide the first hardness of approximation result for the Euclidean k-median problem. Furthermore, we study the hardness of approximation for the Euclidean k-means/k-median problems in the bi-criteria setting where an algorithm is allowed to choose more than k centers. That is, bi-criteria approximation algorithms are allowed to output β k centers (for constant β>1) and the approximation ratio is computed with respect to the optimal k-means/k-median cost. In this setting, we show the first hardness of approximation result for the Euclidean k-median problem for any β < 1.015, assuming UGC. We also show a similar bi-criteria hardness of approximation result for the Euclidean k-means problem with a stronger bound of β < 1.28, again assuming UGC.