A constant factor approximation algorithm for fault-tolerant k-Median

In this paper, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of classical k-median problem, each client j needs to be assigned to at least r_j > 1 distinct open facilities. The service cost of j is the sum of its distances to the r_j facilities, and the k-median constraint restricts the number of open facilities to at most k. Previously, a constant factor was known only for the special case when all r_j s are the same, and a logarithmic approximation ratio was known for the general case. In addition, we present the first polynomial time algorithm for the fault- Tolerant k-median problem on a path or a HST by showing that the corresponding LP always has an integral optimal so-lution. We also consider the fault-tolerant facility location problem, where the service cost of j can be a weighted sum of its distance to the r_j facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.