Improved Bi-point Rounding Algorithms and a Golden Barrier for $k$-Median

Kishen N. Gowda, Thomas Pensyl, Aravind Srinivasan +1

The current best approximation algorithms for $k$-median rely on first obtaining a structured fractional solution known as a bi-point solution, and then rounding it to an integer s…