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

The metric \(k\) -median problem is a classical and widely studied objective for data clustering, with applications in data analysis, computer vision, genomics, and facility location. 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 increasingly-discretized partitioning schemes for the facilities, along with corresponding sets of randomized algorithms and factor-revealing non-linear programs. We show this hierarchy improves upon the current best factor of \(1.3371\) , proving that the third layer of this hierarchy achieves a rounding factor of \(1.3064\) , while no layer can achieve a factor smaller than \(1.2943\) in expectation. Combined with the current best algorithm for bi-point solution generation, we get a \(2.6081\) approximation factor for \(k\) -median. On the negative side, we give a family of bi-point solutions with integrality gap approaching the square root of the golden ratio, approximately \(1.272\) , even when allowed to open \(k+o(k)\) facilities. Altogether, our results substantially narrow the approximation gap for bi-point solutions.