{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:01Z","timestamp":1740122401279,"version":"3.37.3"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T00:00:00Z","timestamp":1619308800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T00:00:00Z","timestamp":1619308800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["12001039","No. 11971349"],"award-info":[{"award-number":["12001039","No. 11971349"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["No. 11871081","No. 11801310"],"award-info":[{"award-number":["No. 11871081","No. 11801310"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2022,11]]},"DOI":"10.1007\/s10878-021-00734-0","type":"journal-article","created":{"date-parts":[[2021,4,25]],"date-time":"2021-04-25T10:29:28Z","timestamp":1619346568000},"page":"2410-2422","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An approximation algorithm for the spherical k-means problem with outliers by local search"],"prefix":"10.1007","volume":"44","author":[{"given":"Yishui","family":"Wang","sequence":"first","affiliation":[]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0018-9184","authenticated-orcid":false,"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Juan","family":"Zou","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2021,4,25]]},"reference":[{"key":"734_CR1","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2017) Better guarantees for $$k$$-means and Euclidean $$k$$-median by primal-dual algorithms. In: Proceedings of FOCS, pp 61-72","DOI":"10.1109\/FOCS.2017.15"},{"key":"734_CR2","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: The advantages of careful seeding. In: Proceedings of SODA, pp 1027-1035"},{"key":"734_CR3","unstructured":"Charikar M, Khuller S, Mount DM, Narasimhan G (2001) Algorithms for facility location problems with outliers. In: Proceedings of SODA, pp 642-651"},{"key":"734_CR4","unstructured":"Chen K (2008) A constant factor approximation algorithm for $$k$$-median clustering with outliers. In: Proceedings of SODA, pp 826-835"},{"key":"734_CR5","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1007612920971","volume":"42","author":"IS Dhillon","year":"2001","unstructured":"Dhillon IS, Modha DS (2001) Concept decompositions for large sparse text data using clustering. Mach Learn 42:143\u2013175","journal-title":"Mach Learn"},{"key":"734_CR6","doi-asserted-by":"crossref","unstructured":"Endo Y, Miyamoto S (2015) Spherical $$k$$-means$$++$$ clustering. In: Proceedings of MDAI, pp 103-114","DOI":"10.1007\/978-3-319-23240-9_9"},{"issue":"2","key":"734_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1145\/3301446","volume":"15","author":"Z Friggstad","year":"2019","unstructured":"Friggstad Z, Khodamoradi K, Rezapour M, Salavatipour MR (2019) Approximation schemes for clustering with outliers. ACM Trans Algorithms 15(2):26","journal-title":"ACM Trans Algorithms"},{"key":"734_CR8","doi-asserted-by":"crossref","unstructured":"Friggstad Z, Rezapour M, Salavatipour MR (2016) Local search yields a PTAS for $$k$$-means in doubling metrics. In: Proceedings of FOCS, pp 365-374","DOI":"10.1109\/FOCS.2016.47"},{"key":"734_CR9","doi-asserted-by":"crossref","unstructured":"Gupta S, Kumar R, Lu K, Moseley B, Vassilvitskii S (2017) Local search methods for $$k$$-means with outliers. In: Proceedings of VLDB, pp 757-768","DOI":"10.14778\/3067421.3067425"},{"issue":"10","key":"734_CR10","doi-asserted-by":"publisher","first-page":"1","DOI":"10.18637\/jss.v050.i10","volume":"50","author":"K Hornik","year":"2012","unstructured":"Hornik K, Feinerer I, Kober M, Buchta C (2012) Spherical $$k$$-means clustering. J Stat Softw 50(10):1\u201322","journal-title":"J Stat Softw"},{"key":"734_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 $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. J ACM 48:274\u2013296","journal-title":"J ACM"},{"key":"734_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 $$k$$-means clustering. Comput Geom Theory Appl 28:89\u2013112","journal-title":"Comput Geom Theory Appl"},{"key":"734_CR13","doi-asserted-by":"publisher","DOI":"10.1007\/s10878-020-00537-9","author":"M Li","year":"2020","unstructured":"Li M (2020) The bi-criteria seeding algorithms for two variants of $$k$$-means problem. J Comb Optim. https:\/\/doi.org\/10.1007\/s10878-020-00537-9","journal-title":"J Comb Optim"},{"key":"734_CR14","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1007\/s10898-019-00779-w","volume":"76","author":"M Li","year":"2020","unstructured":"Li M, Xu D, Zhang D, Zou J (2020) The seeding algorithms for spherical $$k$$-means clustering. J Glob Optim 76:695\u2013708","journal-title":"J Glob Optim"},{"key":"734_CR15","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":"734_CR16","doi-asserted-by":"crossref","unstructured":"Mahajan M, Nimbhorkar P, Varadarajan K (2009) The planar $$k$$-means problem is NP-hard. In: Proceedings of WALCOM, pp 274-285","DOI":"10.1007\/978-3-642-00202-1_24"},{"key":"734_CR17","doi-asserted-by":"crossref","unstructured":"Makarychev K, Makarychev Y, Sviridenko M, Ward J (2016) A bi-criteria approximation algorithm for $$k$$-means. In: Proceedings of APPROX and RANDOM, pp 14:1-14:20","DOI":"10.19086\/da.876"},{"key":"734_CR18","unstructured":"Wei D (2016) A constant-factor bi-criteria approximation guarantee for $$k$$-means++. In: Proceedings of NIPS, pp 604-612"},{"key":"734_CR19","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.06.029","author":"D Zhang","year":"2020","unstructured":"Zhang D, Cheng Y, Li M, Wang Y, Xu D (2020) Approximation algorithms for spherical $$k$$-means problem using local search scheme. Theor Comput Sci. https:\/\/doi.org\/10.1016\/j.tcs.2020.06.029","journal-title":"Theor Comput Sci"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00734-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-021-00734-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-021-00734-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,14]],"date-time":"2022-10-14T20:18:33Z","timestamp":1665778713000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-021-00734-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,4,25]]},"references-count":19,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,11]]}},"alternative-id":["734"],"URL":"https:\/\/doi.org\/10.1007\/s10878-021-00734-0","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2021,4,25]]},"assertion":[{"value":"7 April 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 April 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}