English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

New Approximability Results for the Robust k-Median Problem

MPS-Authors
/persons/resource/persons79216

Bhattacharya,  Sayan
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons44225

Chalermsook,  Parinya
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons45021

Mehlhorn,  Kurt
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

/persons/resource/persons71827

Neumann,  Adrian
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource
No external resources are shared
Fulltext (restricted access)
There are currently no full texts shared for your IP range.
Fulltext (public)

arXiv:1309.4602.pdf
(Preprint), 2MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Bhattacharya, S., Chalermsook, P., Mehlhorn, K., & Neumann, A. (2013). New Approximability Results for the Robust k-Median Problem. Retrieved from http://arxiv.org/abs/1309.4602.


Cite as: https://hdl.handle.net/11858/00-001M-0000-0024-5E4F-6
Abstract
We consider a robust variant of the classical $k$-median problem, introduced by Anthony et al. \cite{AnthonyGGN10}. In the \emph{Robust $k$-Median problem}, we are given an $n$-vertex metric space $(V,d)$ and $m$ client sets $\set{S_i \subseteq V}_{i=1}^m$. The objective is to open a set $F \subseteq V$ of $k$ facilities such that the worst case connection cost over all client sets is minimized; in other words, minimize $\max_{i} \sum_{v \in S_i} 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 $\Omega(\log m/ \log \log m)$ approximation hardness, unless ${\sf NP} \subseteq \bigcap_{\delta >0} {\sf DTIME}(2^{n^{\delta}})$. This hardness 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.