A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median

作者：Hajiaghayi Mohammadtaghi; Hu Wei; Li Jian^*; Li Shi; Saha Barna

来源：ACM Transactions on Algorithms, 2016, 12(3): 36.

DOI：10.1145/2854153

• Facility location
• k-median
• approximation algorithms
• fault-tolerance

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.
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 r(j) facilities. We give a simple constant factor approximation algorithm, generalizing several previous results that work only for nonincreasing weight vectors.

• 出版日期2016-6
• 单位清华大学