Improved approximation algorithm for fault-tolerant facility placement

Publication date 20 November 2015

Abstract: We consider the Fault-Tolerant Facility Placement problem (

F T F P

), which is a generalization of the classical Uncapacitated Facility Location problem (

U F L

). In the

F T F P

problem we have a set of clients

C

and a set of facilities

F

. Each facility

i i n F

can be opened many times. For each opening of facility

i

we pay

f_{i} g e q 0

. Our goal is to connect each client

j i n C

with

r_{j} g e q 1

open facilities in a way that minimizes the total cost of open facilities and established connections. In a series of recent papers

F T F P

was essentially reduced to

F T F L

and then to

U F L

showing it could be approximated with ratio

1.575

. In this paper we show that

F T F P

can actually be approximated even better. We consider approximation ratio as a function of

r = m i n_{j i n C} r_{j}

(minimum requirement of a client). With increasing

r

the approximation ratio of our algorithm

l a m b d a_{r}

converges to one. Furthermore, for

r > 1

the value of

l a m b d a_{r}

is less than 1.463 (hardness of approximation of

U F L

). We also show a lower bound of 1.278 for the approximability of the Fault-Tolerant Facility Location problem (

F T F L

) for arbitrary

r

. Already for

r > 3

we obtain that

F T F P

can be approximated with ratio 1.275, showing that under standard complexity theoretic assumptions

F T F P

is strictly better approximable than

F T F L

.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Improved approximation algorithm for fault-tolerant facility placement