SCIENCE@home

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

M. Hajiaghayi,J. Li,Shi Li,B. Saha

Published 2013 in ACM-SIAM Symposium on Discrete Algorithms

ABSTRACT

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 at most 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.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-46 of 46 references · Page 1 of 1

CITED BY

Showing 1-31 of 31 citing papers · Page 1 of 1