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

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 solution. We improve this second step by unifying and refining previous approaches. We describe a hierarchy of increasinglycomplex partitioning schemes for the facilities, along with corresponding sets of algorithms and factor-revealing non-linear programs. We prove that the third layer of this hierarchy is a 2.613approximation, improving upon the current best ratio of 2.675, while no layer can be proved better than 2.588 under the proposed analysis. On the negative side, we give a family of bi-point solutions which cannot be approximated better than the square root of the golden ratio, even if allowed to open k + o(k) facilities. This gives a barrier to current approaches for obtaining an approximation better than 2 √ φ ≈ 2.544. Altogether we reduce the approximation gap of bi-point solutions by two thirds.