{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T15:30:59Z","timestamp":1743089459524,"version":"3.40.3"},"publisher-location":"Boston, MA","reference-count":15,"publisher":"Springer US","isbn-type":[{"type":"print","value":"9780387307701"},{"type":"electronic","value":"9780387301624"}],"license":[{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2008,1,1]],"date-time":"2008-01-01T00:00:00Z","timestamp":1199145600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2008]]},"DOI":"10.1007\/978-0-387-30162-4_212","type":"book-chapter","created":{"date-parts":[[2008,6,26]],"date-time":"2008-06-26T18:35:05Z","timestamp":1214505305000},"page":"470-473","source":"Crossref","is-referenced-by-count":0,"title":["Local Search for K-medians and Facility Location"],"prefix":"10.1007","author":[{"given":"Kamesh","family":"Munagala","sequence":"first","affiliation":[]}],"member":"297","reference":[{"issue":"3","key":"212_CR1_212","doi-asserted-by":"publisher","first-page":"544","DOI":"10.1137\/S0097539702416402","volume":"33","author":"V. Arya","year":"2004","unstructured":"Arya, V., Garg, N., Khandekar, R., Meyerson, A., Munagala, K., Pandit, V.: Local search heuristics for k-median and facility location problems. SIAM J. Comput. 33(3), 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"212_CR2_212","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M. Charikar","year":"2005","unstructured":"Charikar, M., Guha, S.: Improved combinatorial algorithms for facility location problems. SIAM J. Comput. 34(4), 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"212_CR3_212","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A\u00a0constant-factor approximation algorithm for the k-median problem (extended abstract). In: STOC '99: Proceedings of the thirty-first annual ACM symposium on Theory of computing, pp.\u00a01\u201310. Atlanta, May 1-4 1999","DOI":"10.1145\/301250.301257"},{"issue":"2","key":"212_CR4_212","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"F.A. Chudak","year":"2005","unstructured":"Chudak, F.A., Williamson, D.P.: Improved approximation algorithms for capacitated facility location problems. Math. Program. 102(2), 207\u2013222 (2005)","journal-title":"Math. Program."},{"key":"212_CR5_212","first-page":"119","volume-title":"Discrete Location Theory","author":"G. Cornuejols","year":"1990","unstructured":"Cornuejols, G., Nemhauser, G.L., Wolsey, L.A.: The uncapacitated facility location problem. In: Discrete Location Theory, pp.\u00a0119\u2013171. Wiley, New York (1990)"},{"issue":"6","key":"212_CR6_212","doi-asserted-by":"publisher","first-page":"795","DOI":"10.1145\/950620.950621","volume":"50","author":"K. Jain","year":"2003","unstructured":"Jain, K., Mahdian, M., Markakis, E., Saberi, A., Vazirani, V.V.: Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J.\u00a0ACM 50(6), 795\u2013824 (2003)","journal-title":"J. ACM"},{"issue":"2","key":"212_CR7_212","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K. Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and k-median problems using the primal-dual schema and lagrangian relaxation. J.\u00a0ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"212_CR8_212","doi-asserted-by":"publisher","DOI":"10.1002\/9780470316801","volume-title":"Finding Groups in Data: An Introduction to Cluster Analysis","author":"L. Kaufman","year":"1990","unstructured":"Kaufman, L., Rousseeuw, P.J.: Finding Groups in Data: An Introduction to Cluster Analysis. Wiley, New York (1990)"},{"key":"212_CR9_212","unstructured":"Korupolu, M.R., Plaxton, C.G., Rajaraman, R.: Analysis of a\u00a0local search heuristic for facility location problems. In: SODA '98: Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, pp.\u00a01\u201310. San Francisco, USA; 25\u201326 January 1998"},{"issue":"4","key":"212_CR10_212","doi-asserted-by":"publisher","first-page":"643","DOI":"10.1287\/mnsc.9.4.643","volume":"9","author":"A.A. Kuehn","year":"1963","unstructured":"Kuehn, A.A., Hamburger, M.J.: A\u00a0heuristic program for locating warehouses. Management Sci. 9(4), 643\u2013666 (1963)","journal-title":"Management Sci."},{"key":"212_CR11_212","doi-asserted-by":"crossref","unstructured":"Lin, J.-H., Vitter, J.S.: \u03b5-approximations with minimum packing constraint violation (extended abstract). In: STOC '92: Proceedings of the twenty-fourth annual ACM symposium on Theory of computing, pp.\u00a0771\u2013782. Victoria (1992)","DOI":"10.1145\/129712.129787"},{"key":"212_CR12_212","doi-asserted-by":"crossref","unstructured":"Mahdian, M., P\u00e1l, M.: Universal facility location. In: European Symposium on Algorithms, pp.\u00a0409\u2013421. Budapest, Hungary, September 16\u201319 2003","DOI":"10.1007\/978-3-540-39658-1_38"},{"key":"212_CR13_212","unstructured":"Ng, R.T., Han, J.: Efficient and effective clustering methods for spatial data mining. In: Proc. Symp. on Very Large Data Bases (VLDB), pp.\u00a0144\u2013155. Santiago de Chile, 12\u201315 September 1994"},{"key":"212_CR14_212","doi-asserted-by":"crossref","unstructured":"P\u00e1l, M., Tardos, \u00c9., Wexler, T.: Facility location with nonuniform hard capacities. In: Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, pp.\u00a0329\u2013338. Las Vegas, 14\u201317 October 2001","DOI":"10.1109\/SFCS.2001.959907"},{"key":"212_CR15_212","first-page":"265","volume-title":"Proceedings of the 29th Annual ACM Symposium on Theory of Computing (STOC)","author":"D.B. Shmoys","year":"1997","unstructured":"Shmoys, D.B., Tardos, \u00c9., and Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp.\u00a0265\u2013274. El Paso, 4\u20136 May 1997"}],"container-title":["Encyclopedia of Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-0-387-30162-4_212","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,3]],"date-time":"2022-09-03T03:13:48Z","timestamp":1662174828000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-0-387-30162-4_212"}},"subtitle":["2001; Arya, Garg, Khandekar, Meyerson, Munagala, Pandit"],"short-title":[],"issued":{"date-parts":[[2008]]},"ISBN":["9780387307701","9780387301624"],"references-count":15,"URL":"https:\/\/doi.org\/10.1007\/978-0-387-30162-4_212","relation":{},"subject":[],"published":{"date-parts":[[2008]]}}}