Improved algorithms for fault tolerant facility location

We consider a generalization of the classical facility location problem, where we reguire the solution to be fault-tolerant. Every demand point; is served by rj facilities instead of just one. The facilities other than the closest one are "backup" facilities for that demand, and will be used only if the closer facility (or the link to it) fails. Hence, for any demand, we assign non-increasing weights to the routing costs to farther facilities. The cost of assignment for demand J is the weighted linear combination of the assignment costs to its rj closest open facilities. We wish to minimize the sum of the cost of opening the facilities and the assignment cost of each demand J. We obtain a factor 4 approximation to this problem through the application of various rounding technigues to the linear relaxation of an integer program formulation. We further improve this result to 3.16 using randomization and to 2.47 using greedy local-search type technigues. Copyright © 2009 ACM, Inc.

Duke Scholars

Author Kamesh Munagala Computer Science