Separating $$k\text {-}\textsc {Median}$$ from the Supplier Version

Separating $$k\text {-}\textsc {Median}$$ from the Supplier Version

연구 분야: Software Development

학회: International Conference on Integer Programming and Combinatorial Optimization

Given a metric space (V, d) along with an integer k, the problem asks to open k centers to minimize , where . While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set is given with the restriction , the best known hardness for these two versions are and respectively, using the same reduction from . We prove the following two results separating them. We give a 1.546-parameterized approximation algorithm that runs in time . Since is proved to be the optimal approximation ratio for the supplier version in the parameterized setting, this result separates the original from the supplier version. We prove a 1.416-hardness for polynomial-time algorithms assuming the Unique Games Conjecture. This is achieved via a new fine-grained hardness of for small set sizes. Our upper bound and lower bound are derived from almost the same expression, with the only difference coming from the well-known separation between the powers of LP and SDP on (hypergraph) vertex cover.