Paper Info
Title
Improved Approximation Algorithm for Fault-Tolerant Facility Placement.
Abstract
We consider the Fault-Tolerant Facility Placement problem (FTFP), which is a generalization of the classical Uncapacitated Facility Location problem (UFL). In the FTFP problem we have a set of clients C and a set of facilities F. Each facility i is an element of F can be opened many times. For each opening of facility i we pay f(i) >= 0. Our goal is to connect each client j is an element of C with r(j) >= 1 open facilities in a way that minimizes the total cost of open facilities and established connections. In a series of recent papers FTFP was essentially reduced to Fault-Tolerant Facility Location problem (FTFL) and then to UFL showing it could be approximated with ratio 1.575. In this paper we show that FTFP can actually be approximated even better. We consider approximation ratio as a function of r = min(j is an element of C) r(j) (minimum requirement of a client). With increasing r the approximation ratio of our algorithm lambda(r) converges to one. Furthermore, for r > 1 the value of lambda(r) is less than 1.463 (hardness of approximation of UFL). We also show a lower bound of 1.278 for the approximability of the FTFL for arbitrary r. Already for r > 3 we obtain that FTFP can be approximated with ratio 1.275, showing that under standard complexity theoretic assumptions FTFP is strictly better approximable than FTFL.
Year
DOI
Venue
2013
10.1007/978-3-319-18263-6_6
Lecture Notes in Computer Science
DocType
Volume
ISSN
Journal
8952
0302-9743
Citations 
PageRank 
References 
0
0.34
11
Authors
2
Name
Order
Citations
PageRank
Bartosz Rybicki1434.80
Jaroslaw Byrka252331.45