A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median
Lists
Only you see this
Abstract
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 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 at most k. Previously, a constant factor was known only for the special case when all rjs 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 solution. 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 rj facilities. We give a simple constant factor approximation algorithm, generalizing several previous results which only work for nonincreasing weight vectors.
BibTeX
@inproceedings{hajiaghayi2014constant,
author = {MohammadTaghi Hajiaghayi and Wei Hu and Jian Li and Shi Li and Barna Saha},
title = {{A Constant Factor Approximation Algorithm for Fault-Tolerant k-Median}},
booktitle = {SODA},
year = {2014},
doi = {10.1137/1.9781611973402.1},
}Loading related content...