Journal
JOURNAL OF THE ACM
Volume 50, Issue 6, Pages 795-824Publisher
ASSOC COMPUTING MACHINERY
DOI: 10.1145/950620.950621
Keywords
approximation algorithms; dual-fitting method; facility location problem; primal-dual method
Ask authors/readers for more resources
In this article, we will formalize the method of dual fitting and the idea of factor-revealing LP. This combination is used to design and analyze two greedy algorithms for the metric uncapacitated facility location problem. Their approximation factors are 1.861 and 1.61, with running times of O(m log m) and O(n(3)), respectively, where n is the total number of vertices and m is the number of edges in the underlying complete bipartite graph between cities and facilities. The algorithms are used to improve recent results for several variants of the problem.
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