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.
Joint work with Thomas Pensyl, Aravind Srinivasan and Khoa Trinh.
Kishen is a third-year PhD student at the University of Maryland, College Park, advised by Laxman Dhulipala and Aravind Srinivasan. His research interests broadly lie in efficient parallel graph algorithms, approximation and parameterized algorithms for problems in combinatorial optimization with a focus on algorithmic fairness.