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

arXiv: https://arxiv.org/abs/2210.13395 · HTML: https://mlsanity.com/paper/2210.13395/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Oct 2022.

## Built on by (most cited first, 2 of 2)

- [A Broader View on Clustering under Cluster-Aware Norm Objectives](https://mlsanity.com/paper/2512.06211/) (2025)
- [Simple KNN-Based Outlier Detection Achieves Robust Clustering](https://mlsanity.com/paper/2605.07130/) (2026)

## Abstract (arXiv)

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-complex 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.613-approximation, 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.