An Improved Local Search Algorithm for k-Median

Vincent Cohen-Addad, Anupam Gupta, Lunjia Hu +2

We present a new local-search algorithm for the $k$-median clustering problem. We show that local optima for this algorithm give a $(2.836+\epsilon )$-approximation; our result improves up…