New approximability results for the robust k-median problem

We consider a variant of the classical k-median problem, introduced by Anthony et al. [1]. In the Robust k-Median problem, we are given an n-vertex metric space (V, d) and m client sets {S_i ⊆ V} _i=1 ^m. We want to open a set F ⊆ V of k facilities such that the worst case connection cost over all client sets is minimized; that is, minimize max_i Σ_v∈Si d(F, v). Anthony et al. showed an O(log m) approximation algorithm for any metric and APX-hardness even in the case of uniform metric. In this paper, we show that their algorithm is nearly tight by providing Ω(log m/ log log m) approximation hardness, unless NP ⊆ ∩_δ>0 DTIME(2^nδ). This result holds even for uniform and line metrics. To our knowledge, this is one of the rare cases in which a problem on a line metric is hard to approximate to within logarithmic factor. We complement the hardness result by an experimental evaluation of different heuristics that shows that very simple heuristics achieve good approximations for realistic classes of instances.