{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T09:05:16Z","timestamp":1664355916831},"reference-count":28,"publisher":"Elsevier BV","issue":"1","license":[{"start":{"date-parts":[[2000,10,1]],"date-time":"2000-10-01T00:00:00Z","timestamp":970358400000},"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":["Journal of Algorithms"],"published-print":{"date-parts":[[2000,10]]},"DOI":"10.1006\/jagm.2000.1100","type":"journal-article","created":{"date-parts":[[2002,9,17]],"date-time":"2002-09-17T23:19:36Z","timestamp":1032304776000},"page":"146-188","source":"Crossref","is-referenced-by-count":163,"title":["Analysis of a Local Search Heuristic for Facility Location Problems"],"prefix":"10.1006","volume":"37","author":[{"given":"Madhukar R.","family":"Korupolu","sequence":"first","affiliation":[]},{"given":"C.Greg","family":"Plaxton","sequence":"additional","affiliation":[]},{"given":"Rajmohan","family":"Rajaraman","sequence":"additional","affiliation":[]}],"member":"78","reference":[{"key":"10.1006\/jagm.2000.1100_RF1","series-title":"Network Flows: Theory, Algorithms, and Applications","author":"Ahuja","year":"1993"},{"key":"10.1006\/jagm.2000.1100_RF2","series-title":"Proceedings of the 30th Annual ACM Symposium on Theory of Computing","article-title":"Approximation schemes for Euclidean k-medians and related problems","author":"Arora","year":"1998"},{"key":"10.1006\/jagm.2000.1100_RF3","series-title":"Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science","article-title":"Improved combinatorial algorithms for the facility location and k-median problems","author":"Charikar","year":"1999"},{"key":"10.1006\/jagm.2000.1100_RF4","series-title":"Proceedings of the 31st Annual ACM Symposium on Theory of Computing","article-title":"A constant-factor approximation algorithm for the k-median problem","author":"Charikar","year":"1999"},{"key":"10.1006\/jagm.2000.1100_RF5","series-title":"Proceedings of the 6th Conference on Integer Programming and Combinatorial Optimization","article-title":"Improved approximation algorithms for the uncapacitated facility location problem","author":"Chudak","year":"1998"},{"key":"10.1006\/jagm.2000.1100_RF6","series-title":"Proceedings of the 10th Annual ACM-SIAM Symposium on Discrete Algorithms","article-title":"Improved approximation algorithms for a capacitated facility location problem","author":"Chudak","year":"1999"},{"key":"10.1006\/jagm.2000.1100_RF7","series-title":"Proceedings of the 7th Conference on Integer Programming and Combinatorial Optimization","article-title":"Improved approximation algorithms for capacitated facility location problems","author":"Chudak","year":"1999"},{"key":"10.1006\/jagm.2000.1100_RF8","series-title":"Discrete Location Theory","first-page":"119","article-title":"The uncapacitated facility location problem","author":"Corne\u00fajols","year":"1990"},{"key":"10.1006\/jagm.2000.1100_RF9","unstructured":"G. Diehr, An Algorithm for the p-Median Problem, Technical Report, 191, Western Management Science Institute, UCLA, June 1972."},{"key":"10.1006\/jagm.2000.1100_RF10","series-title":"Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science","article-title":"Faster and simpler algorithms for multicommodity flow and other traditional packing problems","author":"Garg","year":"1998"},{"key":"10.1006\/jagm.2000.1100_RF11","series-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","article-title":"Greedy strikes back: Improved facility location algorithms","author":"Guha","year":"1998"},{"key":"10.1006\/jagm.2000.1100_RF12","doi-asserted-by":"crossref","first-page":"148","DOI":"10.1007\/BF01581035","article-title":"Heuristics for the fixed cost median problem","volume":"22","author":"Hochbaum","year":"1982","journal-title":"Math. Programming"},{"key":"10.1006\/jagm.2000.1100_RF13","series-title":"Approximation Algorithms for NP-hard Problems","first-page":"346","article-title":"Various notions of approximations: Good, better, best, and more","author":"Hochbaum","year":"1995"},{"key":"10.1006\/jagm.2000.1100_RF14","series-title":"Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science","article-title":"Primal-dual approximation algorithms for metric facility location and k-median problems","author":"Jain","year":"1999"},{"key":"10.1006\/jagm.2000.1100_RF15","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1007\/BF02579150","article-title":"A new polynomial-time algorithm for linear programming","volume":"4","author":"Karmarkar","year":"1984","journal-title":"Combinatorica"},{"key":"10.1006\/jagm.2000.1100_RF16","first-page":"191","article-title":"A polynomial algorithm for linear programming","volume":"20","author":"Khachiyan","year":"1979","journal-title":"Soviet Math. Dokl."},{"key":"10.1006\/jagm.2000.1100_RF17","series-title":"Proceedings of the 9th Annual ACM-SIAM Symposium on Discrete Algorithms","article-title":"Analysis of a local search heuristic for facility location problems","author":"Korupolu","year":"1998"},{"key":"10.1006\/jagm.2000.1100_RF18","doi-asserted-by":"crossref","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","article-title":"A heuristic program for locating warehouses","volume":"9","author":"Kuehn","year":"1963","journal-title":"Management Sci."},{"key":"10.1006\/jagm.2000.1100_RF19","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1016\/0020-0190(92)90208-D","article-title":"Approximation algorithms for geometric median problems","volume":"44","author":"Lin","year":"1992","journal-title":"Inform. Process. Lett."},{"key":"10.1006\/jagm.2000.1100_RF20","series-title":"Proceedings of the 24th Annual ACM Symposium on Theory of Computing","article-title":"\u03b5-Approximations with minimum packing constraint violations","author":"Lin","year":"1992"},{"key":"10.1006\/jagm.2000.1100_RF21","series-title":"Facilities Location: Models and Methods","author":"Love","year":"1988"},{"key":"10.1006\/jagm.2000.1100_RF22","series-title":"Discrete Location Theory","author":"Mirchandani","year":"1990"},{"key":"10.1006\/jagm.2000.1100_RF23","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1007\/BF01585178","article-title":"An approximation algorithm for the generalized assignment problem","volume":"62","author":"Shmoys","year":"1993","journal-title":"Math. Programming"},{"key":"10.1006\/jagm.2000.1100_RF24","series-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing","article-title":"Approximation algorithms for facility location problems","author":"Shmoys","year":"1997"},{"key":"10.1006\/jagm.2000.1100_RF25","unstructured":"M. Sviridenko, Personal communication, December 1999."},{"key":"10.1006\/jagm.2000.1100_RF26","doi-asserted-by":"crossref","first-page":"955","DOI":"10.1287\/opre.16.5.955","article-title":"Heuristic methods for estimating the generalized vertex median of a weighted graph","volume":"16","author":"Teitz","year":"1968","journal-title":"Oper. Res."},{"key":"10.1006\/jagm.2000.1100_RF27","series-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms","article-title":"Randomized rounding without solving the linear program","author":"Young","year":"1995"},{"key":"10.1006\/jagm.2000.1100_RF28","unstructured":"N. Young, Greedy Approximation Algorithms for k-medians by Randomized Rounding, Technical Report, PCS-TR99-344, Department of Computer Science, Dartmouth College, March 1999."}],"container-title":["Journal of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677400911003?httpAccept=text\/xml","content-type":"text\/xml","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/api.elsevier.com\/content\/article\/PII:S0196677400911003?httpAccept=text\/plain","content-type":"text\/plain","content-version":"vor","intended-application":"text-mining"}],"deposited":{"date-parts":[[2019,5,9]],"date-time":"2019-05-09T03:54:18Z","timestamp":1557374058000},"score":1,"resource":{"primary":{"URL":"https:\/\/linkinghub.elsevier.com\/retrieve\/pii\/S0196677400911003"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000,10]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2000,10]]}},"alternative-id":["S0196677400911003"],"URL":"http:\/\/dx.doi.org\/10.1006\/jagm.2000.1100","relation":{},"ISSN":["0196-6774"],"issn-type":[{"value":"0196-6774","type":"print"}],"subject":["Computational Theory and Mathematics","Computational Mathematics","Control and Optimization"],"published":{"date-parts":[[2000,10]]}}}