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 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 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.
展开▼
