We study fault-tolerant ordered k-median and robust ordered k-median, both as  generalizations of the  ordered k-median problem. In these problems, we are often given a metric space , and asked to open a set of at most k facilities and provide a certain assignment of these facilities to a set of clients, in order to minimize the ordered weighted sum of the induced service costs from all facility-client assignments c is minimized. Here w\inR^{|X|} is a predefined non-increasing non-negative vector, and }c  . In the fault-tolerant problem, every client jhas a requirement r_j and needs to be assigned r_j distinct facilities. The cost of client j is the sum of distances to its assigned facilities . In the robust problem,\vec{c} a parameter m is given and we need to assign some facility to at least m clients. We give polynomial-time\vec{c} constant-factor  approximation algorithms for both problems, which use standard sparsification as well as iterative rounding techniques for LP relaxations . We also consider ordered knapsack median and ordered matroid median, and use the iterative rounding framework to obtain constant-factor approximations as well  .
We study fault-tolerant ordered k-median and robust ordered k-median, both as novel generalizations of the celebrated ordered k-median problem. In ordered k-median, given a metric space (X,d), we need to open a set of k facilities S\subseteq X, such that if :=\{d(j,S):j\in X\} is the service cost vector of connection distances, the objective w^Tc^{\downarrow is minimized. Here w\inR^{|X|} is a predefined non-increasing non-negative vector, and }c^{\downarrow , therefore multiplying larger costs with larger weights . In the fault-tolerant variant of ordered k-median, every j\in X needs to be assigned r_j \geq 1 distinct facilities in S. The service cost of j is now the sum of distances to its assigned facilities , and the objective is still w^T\vec{c}^{\downarrow a parameter m is given and we need to connect the nearest open facility to m points in X. In this case, the service cost vector\vec{c}\in\mathbb{R constant-factor polynomial time approximation algorithms for both problems, based on several novel techniques in LP rounding . We also consider ordered knapsack median and ordered matroid median, and use the same methodology to obtain constant-factor approximations as well . We note that none of the four problems had constant approximations prior to our study .
A
novel
A
celebrated
R
these problems, we are often
ordered k-median,
R
, and asked
(X,d), we need
R
at most k facilities and provide a certain assignment of these facilities to a set of clients, in order to minimize the ordered weighted sum of the induced service costs from all facility-client assignments
k facilities S\subseteq X, such that if
A
:=\{d(j,S):j\in X\} is the service cost vector of connection distances, the objective w^T
A
^{\downarrow
A
^{\downarrow
A
, therefore multiplying larger costs with larger weights
R
problem, every client jhas a requirement r_j and
variant of ordered k-median, every j\in X
R
distinct facilities. The cost of client j is
\geq 1 distinct facilities in S. The service cost of j is now
R
. In the robust problem,
, and the objective is still w^T
A
^{\downarrow
R
assign some facility to at least m clients. We give polynomial-time
connect the nearest open facility to m points in X. In this case, the service cost vector
A
\in\mathbb{R
A
polynomial time
R
which use standard sparsification as well as iterative rounding techniques for LP relaxations
based on several novel techniques in LP rounding
R
iterative rounding framework
same methodology
A
. We note that none of the four problems had constant approximations prior to our study