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

In this article, we consider the fault-tolerant k-median problem and give the first constant factor approximation algorithm for it. In the fault-tolerant generalization of the classical k-median problem, each client j needs to be assigned to at least rj ≥ 1 distinct open facilities. The service cost of j is the sum of its distances to the rj facilities, and the k-median constraint restricts the number of open facilities to atmost k. Previously, a constant factor was known only for the special case when all rjs are the same, and alogarithmic 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 an HST by showing that the corresponding LP always has an integral optimal solution. We also consider the fault-tolerant facility location problem, in which the service cost of j can be a weighted sum of its distance to the rj facilities.We give a simple constant factor approximation algorithm, generalizing several previous results that work only for nonincreasing weight vectors.