Journal
SIAM JOURNAL ON COMPUTING
Volume 34, Issue 4, Pages 803-824Publisher
SIAM PUBLICATIONS
DOI: 10.1137/S0097539701398594
Keywords
approximation algorithms; facility location; local search; combinatorial optimization
Ask authors/readers for more resources
We present improved combinatorial approximation algorithms for the uncapacitated facility location problem. Two central ideas in most of our results are cost scaling and greedy improvement. We present a simple greedy local search algorithm which achieves an approximation ratio of 2.414+epsilon in (O) over tilde( n(2)/epsilon) time. This also yields a bicriteria approximation tradeoff of (1+gamma, 1+ 2/gamma) for facility cost versus service cost which is better than previously known tradeoffs and close to the best possible. Combining greedy improvement and cost scaling with a recent primal-dual algorithm for facility location due to Jain and Vazirani, we get an approximation ratio of 1.853 in (O) over tilde( n(3)) time. This is very close to the approximation guarantee of the best known algorithm which is linear programming ( LP)-based. Further, combined with the best known LP-based algorithm for facility location, we get a very slight improvement in the approximation factor for facility location, achieving 1.728. We also consider a variant of the capacitated facility location problem and present improved approximation algorithms for this.
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