## Abstract

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.

Original language | English |
---|---|

Title of host publication | Algorithm Theory, SWAT 2014 - 14th Scandinavian Symposium and Workshops, Proceedings |

Publisher | SPRINGER |

Pages | 50-61 |

Number of pages | 12 |

Volume | 8503 LNCS |

ISBN (Print) | 9783319084039 |

DOIs | |

Publication status | Published - 2014 |

MoE publication type | A4 Article in a conference publication |

Event | Scandinavian Symposium and Workshops on Algorithm Theory - Copenhagen, Denmark Duration: 2 Jul 2014 → 4 Jul 2014 Conference number: 14 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8503 LNCS |

ISSN (Print) | 03029743 |

ISSN (Electronic) | 16113349 |

### Conference

Conference | Scandinavian Symposium and Workshops on Algorithm Theory |
---|---|

Abbreviated title | SWAT |

Country/Territory | Denmark |

City | Copenhagen |

Period | 02/07/2014 → 04/07/2014 |