{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:36:23Z","timestamp":1759638983250},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T00:00:00Z","timestamp":1519084800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2018,5]]},"DOI":"10.1007\/s10878-018-0261-2","type":"journal-article","created":{"date-parts":[[2018,2,20]],"date-time":"2018-02-20T01:09:14Z","timestamp":1519088954000},"page":"1168-1184","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["A local search approximation algorithm for a squared metric k-facility location problem"],"prefix":"10.1007","volume":"35","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":[[2018,2,20]]},"reference":[{"key":"261_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 (2004) Local search heuristics for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median and facility location problems. SIAM J Comput 33:544\u2013562","journal-title":"SIAM J Comput"},{"key":"261_CR2","doi-asserted-by":"publisher","first-page":"2212","DOI":"10.1137\/070708901","volume":"39","author":"J Byrka","year":"2010","unstructured":"Byrka J, Aardal KI (2010) An optimal bifactor approximation algorithm for the metric uncapacitated facility location problem. SIAM J Comput 39:2212\u20132231","journal-title":"SIAM J Comput"},{"key":"261_CR3","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A (2014) An improved approximation for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median, and positive correlation in budgeted optimization. In: Proceedings of SODA, pp 737\u2013756"},{"key":"261_CR4","doi-asserted-by":"publisher","first-page":"803","DOI":"10.1137\/S0097539701398594","volume":"34","author":"M Charikar","year":"2005","unstructured":"Charikar M, Guha S (2005) Improved combinatorial algorithms for facility location problems. SIAM J Comput 34:803\u2013824","journal-title":"SIAM J Comput"},{"key":"261_CR5","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1006\/jcss.2002.1882","volume":"1","author":"M Charikar","year":"2002","unstructured":"Charikar M, Guha S, Tardos E, Shmoys DB (2002) A constant-factor approximation algorithm for the \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median problem. J Comput Syst Sci 1:129\u2013149","journal-title":"J Comput Syst Sci"},{"key":"261_CR6","doi-asserted-by":"publisher","first-page":"263","DOI":"10.1007\/s00453-007-9032-7","volume":"53","author":"X Chen","year":"1999","unstructured":"Chen X, Chen B (1999) Approximation algorithms for soft-capacitated facility location in capacitated network design. Algorithmica 53:263\u2013297","journal-title":"Algorithmica"},{"key":"261_CR7","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539703405754","volume":"33","author":"FA Chudak","year":"2003","unstructured":"Chudak FA, Shmoys DB (2003) Improved approximation algorithms for the uncapacitated facility location problem. SIAM J Comput 33:1\u201325","journal-title":"SIAM J Comput"},{"key":"261_CR8","doi-asserted-by":"publisher","first-page":"655","DOI":"10.1007\/s10107-014-0821-x","volume":"153","author":"CG Fernandes","year":"2015","unstructured":"Fernandes CG, Meira LA, Miyazawa FK, Pedrosa LL (2015) 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","journal-title":"Math Program"},{"key":"261_CR9","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 (1999) Greedy strikes back: improved facility location Algorithms. J Algorithms 31:228\u2013248","journal-title":"J Algorithms"},{"key":"261_CR10","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 (2003) Greedy facility location algorithms analyzed using dual fitting with factor-revealing LP. J ACM 50:795\u2013824","journal-title":"J ACM"},{"key":"261_CR11","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain K, Vazirani VV (2001) Approximation algorithms for metric facility location and \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"261_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"2","author":"T Kanungo","year":"2004","unstructured":"Kanungo T, Mount DM, Netanyahu NS, Piatko CD, Silverman R, Wu AY (2004) A local search approximation algorithm for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means clustering. Comput Geom Theory Appl 2:89\u2013112","journal-title":"Comput Geom Theory Appl"},{"key":"261_CR13","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 (2013) A 1.488 approximation algorithm for the uncapacitated facility location problem. Inf Comput 222:45\u201358","journal-title":"Inf Comput"},{"key":"261_CR14","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li S, Svensson O (2016) Approximating \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median via pseudo-approximation. SIAM J Comput 45:530\u2013547","journal-title":"SIAM J Comput"},{"key":"261_CR15","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 (2006) Approximation algorithms for metric facility location problems. SIAM J Comput 36:411\u2013432","journal-title":"SIAM J Comput"},{"key":"261_CR16","unstructured":"Shmoys DB, Tardos E, Aardal K (1997) Approximation algorithms for facility location problems. In: Proceedings of SOTC, pp 265\u2013274"},{"key":"261_CR17","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30:389\u2013403","journal-title":"Math Oper Res"},{"key":"261_CR18","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 (2007) A new approximation algorithm for the \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -facility location problem. Theor Comput Sci 384:126\u2013135","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-018-0261-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0261-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0261-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,2,19]],"date-time":"2019-02-19T19:10:41Z","timestamp":1550603441000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0261-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,2,20]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,5]]}},"alternative-id":["261"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0261-2","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,2,20]]},"assertion":[{"value":"20 February 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}