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

Given a metric space (V, d) along with an integer k, the \(k\text {-}\textsc {Median}\) problem asks to open k centers \(C \subseteq V\) to minimize \(\sum _{v \in V} d(v, C)\) , where \(d(v, C) := \min _{c \in C} d(v, c)\) . While the best-known approximation ratio 2.613 holds for the more general supplier version where an additional set \(F \subseteq V\) is given with the restriction \(C \subseteq F\) , the best known hardness for these two versions are \(1+1/e \approx 1.36\) and \(1+2/e \approx 1.73\) respectively, using the same reduction from \(\textsc {Maximum}~k\text {-}\textsc {Coverage} \) . We prove the following two results separating them. 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.