New Results on the Fault-Tolerant Facility Placement Problem

Details New Results on the Fault-Tolerant Facility Placement Problem New Results on the Fault-Tolerant Facility Placement Problem

2011-08-27

arxiv.org/abs/1108.5471v1

Computer Science

Data Structures and Algorithms

5 pages

Scientific paper

We studied the Fault-Tolerant Facility Placement problem (FTFP) which generalizes the uncapacitated facility location problem (UFL). In FTFP, we are given a set F of sites at which facilities can be built, and a set C of clients with some demands that need to be satisfied by different facilities. A client $j$ has demand $r_j$. Building one facility at a site $i$ incurs a cost $f_i$, and connecting one unit of demand from client $j$ to a facility at site $i\in\fac$ costs $d_{ij}$. $d_{ij}$'s are assumed to form a metric. A feasible solution specifies the number of facilities to be built at each site and the way to connect demands from clients to facilities, with the restriction that demands from the same client must go to different facilities. Facilities at the same site are considered different. The goal is to find a solution with minimum total cost. We gave a 1.7245-approximation algorithm to the FTFP problem. Our technique is via a reduction to the Fault-Tolerant Facility Location problem, in which each client has demand $r_j$ but each site can have at most one facility built.

Affiliated with

Also associated with

No associations

Rating

New Results on the Fault-Tolerant Facility Placement Problem does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with New Results on the Fault-Tolerant Facility Placement Problem, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and New Results on the Fault-Tolerant Facility Placement Problem will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-614128