Title: Interpolating between $k$-Median and $k$-Center: Approximation Algorithms for Ordered $k$-Median,
Abstract: We consider a generalization of $k$-median and $k$-center, called the {\em
ordered $k$-median} problem. In this problem, we are given a metric space
$(\mathcal{D},\{c_{ij}\})$ with $n=|\mathcal{D}|$ points, and a non-increasing
weight vector $w\in\mathbb{R}_+^n$, and the goal is to open $k$ centers and
assign each point each point $j\in\mathcal{D}$ to a center so as to minimize
$w_1\cdot\text{(largest assignment cost)}+w_2\cdot\text{(second-largest
assignment cost)}+\ldots+w_n\cdot\text{($n$-th largest assignment cost)}$. We
give an $(18+\epsilon)$-approximation algorithm for this problem. Our
algorithms utilize Lagrangian relaxation and the primal-dual schema, combined
with an enumeration procedure of Aouad and Segev. For the special case of
$\{0,1\}$-weights, which models the problem of minimizing the $\ell$ largest
assignment costs that is interesting in and of by itself, we provide a novel
reduction to the (standard) $k$-median problem showing that LP-relative
guarantees for $k$-median translate to guarantees for the ordered $k$-median
problem; this yields a nice and clean $(8.5+\epsilon)$-approximation algorithm
for $\{0,1\}$ weights.