{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,26]],"date-time":"2026-02-26T11:46:00Z","timestamp":1772106360761,"version":"3.50.1"},"reference-count":19,"publisher":"Elsevier BV","issue":"5","license":[{"start":{"date-parts":[[2002,10,1]],"date-time":"2002-10-01T00:00:00Z","timestamp":1033430400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.elsevier.com\/tdm\/userlicense\/1.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Operations Research Letters"],"published-print":{"date-parts":[[2002,10]]},"DOI":"10.1016\/s0167-6377(02)00162-1","type":"journal-article","created":{"date-parts":[[2002,10,17]],"date-time":"2002-10-17T01:46:23Z","timestamp":1034819183000},"page":"327-332","source":"Crossref","is-referenced-by-count":26,"title":["Improved approximation algorithms for multilevel facility location problems"],"prefix":"10.1016","volume":"30","author":[{"given":"A.A.","family":"Ageev","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"78","reference":[{"key":"10.1016\/S0167-6377(02)00162-1_BIB1","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0020-0190(99)00144-1","article-title":"A 3-approximation algorithm for the k-level uncapacitated facility location problem","volume":"72","author":"Aardal","year":"1999","journal-title":"Inform. Process. Lett."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB2","doi-asserted-by":"crossref","unstructured":"V. Arya, N. Garg, R. Khandekar, A. Meyerson, K. Munagala, V. Pandit, Local search heuristics for k-median and facility location problems, in: Proceedings of the 33rd ACM Symposium on Theory of Computing, ACM Press, New York, 2001, pp. 21\u201329.","DOI":"10.1145\/380752.380755"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB3","doi-asserted-by":"crossref","unstructured":"A.F. Bumb, W. Kern, A simple dual ascent algorithm for the multilevel facility location problem, in: Proceedings of the 4th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX\u20192001), Lecture Notes in Computer Science, Vol. 2129, Springer, Berlin, 2001, pp. 55\u201362.","DOI":"10.1007\/3-540-44666-4_10"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB4","doi-asserted-by":"crossref","unstructured":"M. Charikar, S. Guha, Improved combinatorial algorithms for facility location and k-median problems, in: Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Silver Spring, MD, 1999, pp. 378\u2013388.","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB5","unstructured":"M. Charikar, S. Khuller, D. Mount, G. Narasimhan, Facility location with outliers, in: Proceedings of the 12th Annual ACM\u2013SIAM Symposium on Discrete Algorithms, Washington DC, 2001, pp. 642\u2013651."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB6","unstructured":"F.A. Chudak, Improved approximation algorithms for uncapacited facility location, in: Proceedings of the 6th Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, Vol. 1412, Springer, Berlin, 1998, pp. 180\u2013194."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB7","doi-asserted-by":"crossref","unstructured":"F.A. Chudak, D.B Shmoys, Improved approximation algorithms for the uncapacitated facility location problem, 1998, unpublished manuscript.","DOI":"10.1007\/3-540-69346-7_14"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB8","doi-asserted-by":"crossref","first-page":"269","DOI":"10.1007\/BF01386390","article-title":"A note on two problems in connection with graphs","volume":"1","author":"Dijkstra","year":"1959","journal-title":"Numer. Math."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB9","unstructured":"N.J. Edwards, Approximation algorithms for the multi-level facility location problem, Ph.D. Thesis, 2001; http:\/\/www.orie.cornell.edu\/nedwards\/thesis.oneside.ps."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB10","doi-asserted-by":"crossref","first-page":"228","DOI":"10.1006\/jagm.1998.0993","article-title":"Greedy strikes back","volume":"31","author":"Guha","year":"1999","journal-title":"J. Algorithms"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB11","doi-asserted-by":"crossref","unstructured":"K. Jain, M. Mahdian, A. Saberi, A new greedy approach for facility location problems, in: Proceedings of the 34th ACM Symposium on Theory of Computing Montreal, Quebec, Canada, May 19\u201321, 2002, to appear.","DOI":"10.1145\/509907.510012"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB12","doi-asserted-by":"crossref","first-page":"274","DOI":"10.1145\/375827.375845","article-title":"Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and Lagrangian relaxation","volume":"48","author":"Jain","year":"2001","journal-title":"J. ACM"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB13","unstructured":"M.R. Korupolu, C.G. Plaxton, R. Rajaraman, Analysis of a local search heuristic for facility location problems, in: Proceedings of the 9th Annual ACM\u2013SIAM Symposium on Discrete Algorithms (SODA\u201998), ACM Press, New York, 1998, pp. 1\u201310."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB14","unstructured":"M. Mahdian, Y. Ye, J. Zhang, A 1.52-approximation algorithm for the uncapacitated facility location problem, 2001, manuscript; http:\/\/www.math.mit.edu\/~mahdian\/floc152.ps."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB15","doi-asserted-by":"crossref","unstructured":"A. Meyerson, K. Munagala, S. Plotkin, Cost distance: two metric network design, in: Proceedings of the 41st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, Silver Spring, MD, 2000, pp. 624\u2013630.","DOI":"10.1109\/SFCS.2000.892330"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB16","doi-asserted-by":"crossref","unstructured":"D. Shmoys, E. Tardos, K.I. Aardal, Approximation algorithms for facility location problems, in: Proceedings of the 29th Annual ACM Symposium on the Theory of Computing (STOC\u201997), ACM Press, New York, 1997, pp. 265\u2013274.","DOI":"10.1145\/258533.258600"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB17","doi-asserted-by":"crossref","unstructured":"M. Sviridenko, An improved approximation algorithm for the metric uncapacitated facility location problem, in: Proceedings of the 9th Integer Programming and Combinatorial Optimization Conference, Lecture Notes in Computer Science, Vol. 2337, Springer, Berlin, 2002, pp. 240\u2013257.","DOI":"10.1007\/3-540-47867-1_18"},{"key":"10.1016\/S0167-6377(02)00162-1_BIB18","unstructured":"M. Sviridenko, personal communication."},{"key":"10.1016\/S0167-6377(02)00162-1_BIB19","doi-asserted-by":"crossref","unstructured":"M. Thorup, Quick k-median, k-center, and facility location for sparse graphs, in: Automata, Languages and Programming, 28th International Colloquium (ICALP\u20192001), Lecture Notes in Computer Science, Vol. 2076, Springer, Berlin, 2001, pp. 249\u2013260.","DOI":"10.1007\/3-540-48224-5_21"}],"container-title":["Operations Research Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637702001621?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0167637702001621?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2020,3,10]],"date-time":"2020-03-10T18:53:01Z","timestamp":1583866381000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0167637702001621"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2002,10]]},"references-count":19,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2002,10]]}},"alternative-id":["S0167637702001621"],"URL":"https:\/\/doi.org\/10.1016\/s0167-6377(02)00162-1","relation":{},"ISSN":["0167-6377"],"issn-type":[{"value":"0167-6377","type":"print"}],"subject":[],"published":{"date-parts":[[2002,10]]}}}