Open access
Aug 2026
A \({(2+\varepsilon )}\)-Approximation Algorithm for Metric \({k}\)-Median
This work presents a nontrivial modification of the Greedy algorithm that operates with only [Formula: see text] adaptive phases and develops a novel [Formula: see text]-approximation algorithm tailored for stable instances, where removing any center from an optimal solution increases the cost by at least an [Formula:...
Vincent Cohen-Addad, Fabrizio Grandoni, Euiwoong Lee et al.
· SIAM journal on computing (P... · 0 citations