The approximation threshold for metric k-median
For every fixed , there is a deterministic polynomial-time algorithm which, given a finite rational metric -median instance with specified candidate facilities and , returns with such that , where the running time is polynomial in the binary encoding length of the instance (with the polynomial possibly depending on ).
The deterministic additive approximation (Theorem 6.2) and the rational implementation of Li-Svensson's reduction (Section 6.6) are established in full detail, supporting the headline theorem.
“Theorem 1.1. For every fixed ε > 0, there is a deterministic algorithm which, given a finite rational metric k-median instance with 1 ≤ k ≤ |F|, returns S ⊆ F, |S| ≤ k, such that ∑ j∈J d(j, S) ≤ (1 + 2/e + ε)OPTk. Its running time is polynomial in the binary encoding length of the instance. The polynomial may depend on ε.” · Show in paper