{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:21:58Z","timestamp":1759638118303,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T00:00:00Z","timestamp":1521417600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"name":"Higher Educational Science and Technology Program of Shandong Province","award":["J15LN23"],"award-info":[{"award-number":["J15LN23"]}]},{"name":"Ri-Xin Talents Project of Beijing University of Technology"},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11501412","11531014"],"award-info":[{"award-number":["11501412","11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Beijing Excellent Talents Funding","award":["2014000020124G046"],"award-info":[{"award-number":["2014000020124G046"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2019,2]]},"DOI":"10.1007\/s10878-018-0278-6","type":"journal-article","created":{"date-parts":[[2018,3,19]],"date-time":"2018-03-19T04:15:35Z","timestamp":1521432935000},"page":"439-453","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":17,"title":["Local search approximation algorithms for the k-means problem with penalties"],"prefix":"10.1007","volume":"37","author":[{"given":"Dongmei","family":"Zhang","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chunlin","family":"Hao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dachuan","family":"Xu","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,3,19]]},"reference":[{"key":"278_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2017) Better guarantees for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means and Euclidean \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median by primal-dual algorithms. In: Proceedings of FOCS, pp 61\u201372","DOI":"10.1109\/FOCS.2017.15"},{"key":"278_CR2","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s10994-009-5103-0","volume":"75","author":"D Aloise","year":"2009","unstructured":"Aloise D, Deshpande A, Hansen P, Popat P (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75:245\u2013249","journal-title":"Mach Learn"},{"key":"278_CR3","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":"278_CR4","unstructured":"Bandyapadhyay S, Varadarajan K (2016) On variants of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means clustering. In: Proceedings of SoCG, article no. 14:14:1\u201314:15"},{"key":"278_CR5","doi-asserted-by":"crossref","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A, Trinh K (2017) An improved approximation for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median, and positive correlation in budgeted optimization. ACM Transactions on Algorithms, 13(2): Article No. 23","DOI":"10.1145\/2981561"},{"key":"278_CR6","doi-asserted-by":"crossref","unstructured":"Charikar M, Guha S (1999) Improved combinatorial algorithms for the facility location and \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median problems. In: Proceedings of FOCS, pp 378\u2013388","DOI":"10.1109\/SFFCS.1999.814609"},{"key":"278_CR7","unstructured":"Charikar M, Guha S, Tardos \u00c9, Shmoys DB (1999) A constant-factor approximation algorithm for the \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -median problem. In: Proceedings of STOC, pp 1\u201310"},{"key":"278_CR8","unstructured":"Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642\u2013651"},{"key":"278_CR9","unstructured":"Dasgupta S (2007) The hardness of \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means clustering. Technical report CS2007-0890, University of California, San Diego"},{"key":"278_CR10","unstructured":"Georgogiannis A (2016) Robust \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means: a theoretical revisit. In: Proceedings of NIPS, pp 2883\u20132891"},{"key":"278_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":"278_CR12","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/j.comgeo.2004.03.003","volume":"28","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 28:89\u2013112","journal-title":"Comput Geom Theory Appl"},{"key":"278_CR13","doi-asserted-by":"publisher","first-page":"460","DOI":"10.1007\/s00453-014-9911-7","volume":"73","author":"Y Li","year":"2015","unstructured":"Li Y, Du D, Xiu N, Xu D (2015) Improved approximation algorithms for the facility location problems with linear\/submodular penalties. Algorithmica 73:460\u2013482","journal-title":"Algorithmica"},{"key":"278_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":"278_CR15","unstructured":"Lloyd S (1957) Least squares quantization in PCM. Technical report, Bell Laboratories"},{"key":"278_CR16","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd S (1982) Least squares quantization in PCM. IEEE Trans Inf Theory 28:129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"278_CR17","doi-asserted-by":"crossref","unstructured":"Mahajan M, Nimbhorkar P, Varadarajan K (2009) The planar \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means problem is NP-hard. In: Proceedings of WALCOM, pp 274\u2013285","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"278_CR18","unstructured":"Makarychev K, Makarychev Y, Sviridenko M, Ward J (2016) A bi-criteria approximation algorithm for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means. In: Proceedings of APPROX\/RONDOM, article no. 14, pp 14:1\u201314:20"},{"key":"278_CR19","doi-asserted-by":"publisher","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"J Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek J (2000) On approximate geometric \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -clustering. Discrete Comput Geom 24:61\u201384","journal-title":"Discrete Comput Geom"},{"key":"278_CR20","doi-asserted-by":"publisher","first-page":"2247","DOI":"10.1093\/bioinformatics\/btm320","volume":"23","author":"GC Tseng","year":"2007","unstructured":"Tseng GC (2007) Penalized and weighted \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -means for clustering with scattered objects and prior information in high-throughput biological data. Bioinformatics 23:2247\u20132255","journal-title":"Bioinformatics"},{"key":"278_CR21","doi-asserted-by":"publisher","unstructured":"Wang Y, Xu D, Du D, Wu C An approximation algorithm for \n                    \n                      \n                    \n                    $$k$$\n                    \n                      \n                        k\n                      \n                    \n                  -facility location problem with linear penalties using local search scheme. J Comb Optim. \n                    https:\/\/doi.org\/10.1007\/s10878-016-0080-2","DOI":"10.1007\/s10878-016-0080-2"},{"key":"278_CR22","unstructured":"Ward J (2017) Private communication"},{"key":"278_CR23","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-0278-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0278-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-018-0278-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,3,18]],"date-time":"2019-03-18T21:05:11Z","timestamp":1552943111000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-018-0278-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,3,19]]},"references-count":23,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2019,2]]}},"alternative-id":["278"],"URL":"https:\/\/doi.org\/10.1007\/s10878-018-0278-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2018,3,19]]},"assertion":[{"value":"19 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}