Thumbnail
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

   Open content in new tab
Source: ACM Digital Library