New approximability results for the robust k-median problem

Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn, Adrian Neumann

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

2 Citations (Scopus)


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 {Si ⊆ 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 maxi Σ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). 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.

Original languageEnglish
Title of host publicationAlgorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings
Number of pages12
Volume8503 LNCS
ISBN (Print)9783319084039
Publication statusPublished - 2014
MoE publication typeA4 Article in a conference publication
EventScandinavian Symposium and Workshops on Algorithm Theory - Copenhagen, Denmark
Duration: 2 Jul 20144 Jul 2014
Conference number: 14

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8503 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349


ConferenceScandinavian Symposium and Workshops on Algorithm Theory
Abbreviated titleSWAT


Dive into the research topics of 'New approximability results for the robust k-median problem'. Together they form a unique fingerprint.

Cite this