### Greedy facility location algorithms analyzed using dual fitting with factor-revealing LPGreedy facility location algorithms analyzed using dual fitting with factor-revealing LP

Access Restriction
Subscribed

 Author Jain, Kamal ♦ Mahdian, Mohammad ♦ Markakis, Evangelos ♦ Saberi, Amin ♦ Vazirani, Vijay V. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2003 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword Approximation algorithms ♦ Dual-fitting method ♦ Facility location problem ♦ Primal-dual method Abstract 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 $\textit{O}(\textit{m}$ log $\textit{m})$ and $O(n^{3}),$ respectively, where $\textit{n}$ is the total number of vertices and $\textit{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. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 2003-11-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 50 Issue Number 6 Page Count 30 Starting Page 795 Ending Page 824

#### Open content in new tab

Source: ACM Digital Library