New Approximability Results for the Robust k-Median Problem

Sayan Bhattacharya, Parinya Chalermsook, Kurt Mehlhorn +1

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$-ver…