{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T01:40:08Z","timestamp":1750988408382,"version":"3.41.0"},"publisher-location":"Cham","reference-count":16,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319711492"},{"type":"electronic","value":"9783319711508"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-71150-8_11","type":"book-chapter","created":{"date-parts":[[2017,11,16]],"date-time":"2017-11-16T00:48:21Z","timestamp":1510793301000},"page":"119-124","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A Local Search Approximation Algorithm for a Squared Metric k-Facility Location Problem"],"prefix":"10.1007","author":[{"given":"Dongmei","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yishui","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhenning","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,11,17]]},"reference":[{"key":"11_CR1","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, 544\u2013562 (2004)","journal-title":"SIAM J. Comput."},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka, J., Aardal, K.: An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J. Comput. 39, 2212\u20132231 (2010)","journal-title":"SIAM J. Comput."},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Byrka, J., Pensyl, T., Rybicki, B., Srinivasan, A., Trinh, K.: An improved approximation for $$k$$-median, and positive correlation in budgeted optimization. In: Proceedings of SODA, pp. 737\u2013756 (2014)","DOI":"10.1137\/1.9781611973730.50"},{"key":"11_CR4","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, 803\u2013824 (2005)","journal-title":"SIAM J. Comput."},{"key":"11_CR5","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guha, S., Tardos, \u00c9., Shmoys, D.B.: A constant-factor approximation algorithm for the $$k$$-median problem. In: Proceedings of STOC, pp. 1\u201310 (1999)","DOI":"10.1145\/301250.301257"},{"key":"11_CR6","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak, F.A., Shmoys, D.B.: Improved approximation algorithms for the uncapacitated facility location problem. SIAM J. Comput. 33, 1\u201325 (2003)","journal-title":"SIAM J. Comput."},{"key":"11_CR7","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s10107-014-0821-x","volume":"153","author":"CG Fernandes","year":"2015","unstructured":"Fernandes, C.G., Meira, L.A., Miyazawa, F.K., Pedrosa, L.L.: A systematic approach to bound factor-revealing LPs and its application to the metric and squared metric facility location problems. Math. Program. 153, 655\u2013685 (2015)","journal-title":"Math. Program."},{"key":"11_CR8","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. ACM 50, 795\u2013824 (2003)","journal-title":"J. ACM"},{"key":"11_CR9","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. ACM 48, 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"11_CR10","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha, S., Khuller, S.: Greedy strikes back: improved facility location algorithms. J. Algorithms 31, 228\u2013248 (1999)","journal-title":"J. Algorithms"},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"2","author":"T Kanungoa","year":"2004","unstructured":"Kanungoa, T., Mountb, D.M., Netanyahuc, N.S., Piatkoe, C.D., Silvermand, R., Wu, A.Y.: A local search approximation algorithm for $$k$$-means clustering. Comput. Geometry Theory Appl. 2, 89\u2013112 (2004)","journal-title":"Comput. Geometry Theory Appl."},{"key":"11_CR12","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1016\/j.ic.2012.01.007","volume":"222","author":"S Li","year":"2013","unstructured":"Li, S.: A $$1.488$$ approximation algorithm for the uncapacitated facility location problem. Inf. Comput. 222, 45\u201358 (2013)","journal-title":"Inf. Comput."},{"key":"11_CR13","doi-asserted-by":"crossref","unstructured":"Li, S., Svensson, O.: Approximating $$k$$-median via pseudo-approximation. In: Proceedings of STOC, pp. 901\u2013910 (2016)","DOI":"10.1145\/2488608.2488723"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1137\/S0097539703435716","volume":"36","author":"M Mahdian","year":"2006","unstructured":"Mahdian, M., Ye, Y., Zhang, J.: Approximation algorithms for metric facility location problems. SIAM J. Comput. 36, 411\u2013432 (2006)","journal-title":"SIAM J. Comput."},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"Shmoys, D.B., Tardos, \u00c9., Aardal, K.: Approximation algorithms for facility location problems. In: Proceedings of STOC, pp. 265\u2013274 (1997)","DOI":"10.1145\/258533.258600"},{"key":"11_CR16","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.tcs.2007.05.024","volume":"384","author":"P Zhang","year":"2007","unstructured":"Zhang, P.: A new approximation algorithm for the $$k$$-facility location problem. Theor. Comput. Sci. 384, 126\u2013135 (2007)","journal-title":"Theor. Comput. Sci."}],"container-title":["Lecture Notes in Computer Science","Combinatorial Optimization and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-71150-8_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,27]],"date-time":"2025-06-27T01:09:56Z","timestamp":1750986596000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-71150-8_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319711492","9783319711508"],"references-count":16,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-71150-8_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"17 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Combinatorial Optimization and Applications","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 December 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 December 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoa2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/anl.sjtu.edu.cn\/cocoa2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}