Robust Fault Tolerant uncapacitated facility location

Details Robust Fault Tolerant uncapacitated facility location Robust Fault Tolerant uncapacitated facility location

2009-12-16

arxiv.org/abs/0912.3188v2

Computer Science

Data Structures and Algorithms

Scientific paper

In the uncapacitated facility location problem, given a graph, a set of demands and opening costs, it is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities. This paper concerns the robust fault-tolerant version of the uncapacitated facility location problem (RFTFL). In this problem, one or more facilities might fail, and each demand should be supplied by the closest open facility that did not fail. It is required to find a set of facilities R, so as to minimize the sum of the cost of opening the facilities in R and the cost of assigning all node demands to open facilities that did not fail, after the failure of up to \alpha facilities. We present a polynomial time algorithm that yields a 6.5-approximation for this problem with at most one failure and a 1.5 + 7.5\alpha-approximation for the problem with at most \alpha > 1 failures. We also show that the RFTFL problem is NP-hard even on trees, and even in the case of a single failure.

Affiliated with

Also associated with

No associations

Rating

Robust Fault Tolerant uncapacitated facility location 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 Robust Fault Tolerant uncapacitated facility location, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Robust Fault Tolerant uncapacitated facility location will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-49375