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

arXiv: https://arxiv.org/abs/1307.2808 · HTML: https://mlsanity.com/paper/1307.2808/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 10 Jul 2013.

## Built on by (most cited first, 1 of 1)

- [Tight FPT Approximation for Socially Fair Clustering](https://mlsanity.com/paper/2106.06755/) (2021)

## Abstract (arXiv)

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