Hardness of Approximation of Euclidean $k$-Median

Anup Bhattacharya, Dishant Goyal, Ragesh Jaiswal

The Euclidean $k$-median problem is defined in the following manner: given a set $\mathcal{X}$ of $n$ points in ${\mathbb{R}}^d$, and an integer $k$, find a set $C \subset \mathbb{…