Journal
SIAM JOURNAL ON COMPUTING
Volume 36, Issue 2, Pages 411-432Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539703435716
Keywords
approximation algorithms; facility location problem; greedy method; linear programming
Ask authors/readers for more resources
In this paper we present a 1.52-approximation algorithm for the metric uncapacitated facility location problem, and a 2-approximation algorithm for the metric capacitated facility location problem with soft capacities. Both these algorithms improve the best previously known approximation factor for the corresponding problem, and our soft-capacitated facility location algorithm achieves the integrality gap of the standard linear programming relaxation of the problem. Furthermore, we will show, using a result of Thorup, that our algorithms can be implemented in quasi-linear time.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available