Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median
ACM Transactions on Probabilistic Machine Learning · 23.05.2026
DOI: 10.1145/3817044 ↗Kurz gefasst
Fachartikel in der Zeitschrift ACM Transactions on Probabilistic Machine Learning, online erschienen am 23.05.2026. Verfasst von Kishen N Gowda und 3 weiteren Autor:innen. Die Arbeit nennt 34 Literaturangaben.
Abstract (Originalsprache)
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.
Zitieren
APA
Gowda, K. N., Pensyl, T., Srinivasan, A., & Trinh, K. (2026). Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median. ACM Transactions on Probabilistic Machine Learning. https://doi.org/10.1145/3817044
Vancouver
Gowda KN, Pensyl T, Srinivasan A, Trinh K. Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median. ACM Transactions on Probabilistic Machine Learning. 2026. doi:10.1145/3817044
BibTeX
@article{Gowda2026,
author = {Gowda, Kishen N and Pensyl, Thomas and Srinivasan, Aravind and Trinh, Khoa},
title = {Improved Bi-point Rounding Algorithms and a Golden Barrier for \(k\) -Median},
journal = {ACM Transactions on Probabilistic Machine Learning},
year = {2026},
doi = {10.1145/3817044}
}
EUVIMED