# Item

ITEM ACTIONSEXPORT

Released

Paper

#### New Approximability Results for the Robust k-Median Problem

##### MPS-Authors

##### 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.