### Approximation algorithms for metric facility location and $\textit{k}-Median$ problems using the primal-dual schema and Lagrangian relaxationApproximation algorithms for metric facility location and $\textit{k}-Median$ problems using the primal-dual schema and Lagrangian relaxation

Access Restriction
Subscribed

 Author Jain, Kamal ♦ Vazirani, Vijay V. Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©2001 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword k-median problem ♦ Lagrangian relaxation ♦ Approximation algorithms ♦ Facility location problem ♦ Linear programming Abstract We present approximation algorithms for the metric uncapacitated facility location problem and the metric $\textit{k}-median$ problem achieving guarantees of 3 and 6 respectively. The distinguishing feature of our algorithms is their low running time: $\textit{O(m}$ $log\textit{m})$ and $\textit{O(m}$ $log\textit{m(L}$ + log $(\textit{n})))$ respectively, where $\textit{n}$ and $\textit{m}$ are the total number of vertices and edges in the underlying complete bipartite graph on cities and facilities. The main algorithmic ideas are a new extension of the primal-dual schema and the use of Lagrangian relaxation to derive approximation algorithms. 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 2001-03-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 48 Issue Number 2 Page Count 23 Starting Page 274 Ending Page 296

#### Open content in new tab

Source: ACM Digital Library