An Approximation Algorithm for the Fault Tolerant Metric Facility Location Problem |
| |
Authors: | Kamal Jain\thanks{One Microsoft Way Redmond WA USA kamalj@microsoftcom and Vijay V Vazirani |
| |
Affiliation: | (1) One Microsoft Way, Redmond, WA 98007, USA;(2) College of Computing, Georgia Institute of Technology, Atlanta, GA 30332–0280, USA |
| |
Abstract: | We consider a fault tolerant version of the metric facility location
problem in which every city, j, is required to be connected to r
j
facilities. We give the first non-trivial approximation algorithm for
this problem, having an approximation guarantee of 3 · H
k
, where
k is the maximum requirement and H
k
is the kth harmonic
number. Our algorithm is along the lines of 2] for the
generalized Steiner network problem. It runs in phases, and each
phase, using a generalization of the primal–dual algorithm of
5] for the metric facility location problem, reduces the
maximum residual requirement by one. |
| |
Keywords: | Approximation algorithms Facility location Fault tolerance Linear programming |
本文献已被 SpringerLink 等数据库收录! |
|