A $(2+\epsilon )$-Approximation Algorithm for Metric $k$-Median

Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee +2

In the classical NP-hard metric $k$-median problem, we are given a set of $n$ clients and centers with metric distances between them, along with an integer parameter $k\ge 1$. The…