Approximating κ-Median via pseudo-approximation

We present a novel approximation algorithm for κ-median that achieves an approximation guarantee of 1 + √3 + ϵ, improving upon the decade-old ratio of 3 + ϵ. Our improved approximation ratio is achieved by exploiting the power of pseudo-approximation. More specifically, our approach is based on two components, each of which, we believe, is of independent interest. First, we show that in order to give an α-approximation algorithm for κ-median, it is sufficient to give a pseudo-approximation algorithm that finds an α-approximate solution by opening κ + O(1) facilities. This is a rather surprising result as there exist instances for which opening κ + 1 facilities may lead to a significantly smaller cost than that of opening only κ facilities. Second, we give such a pseudo-approximation algorithm with α = 1+ √3 + ϵ. Prior to our work, it was not even known whether opening κ + o(k) facilities would help improve the approximation ratio.