{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,8]],"date-time":"2025-11-08T13:16:57Z","timestamp":1762607817864,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T00:00:00Z","timestamp":1586908800000},"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":["11531014","61772005"],"award-info":[{"award-number":["11531014","61772005"]}],"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":["11871081"],"award-info":[{"award-number":["11871081"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003392","name":"Natural Science Foundation of Fujian Province","doi-asserted-by":"publisher","award":["2017J01753"],"award-info":[{"award-number":["2017J01753"]}],"id":[{"id":"10.13039\/501100003392","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100015642","name":"Higher Educational Science and Technology Program of Shandong Province","doi-asserted-by":"crossref","award":["J17KA171"],"award-info":[{"award-number":["J17KA171"]}],"id":[{"id":"10.13039\/501100015642","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100007129","name":"Natural Science Foundation of Shandong Province","doi-asserted-by":"publisher","award":["ZR2019MA032"],"award-info":[{"award-number":["ZR2019MA032"]}],"id":[{"id":"10.13039\/501100007129","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,10]]},"DOI":"10.1007\/s10878-020-00569-1","type":"journal-article","created":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T13:04:12Z","timestamp":1586955852000},"page":"1977-1994","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["The seeding algorithm for spherical k-means clustering with penalties"],"prefix":"10.1007","volume":"44","author":[{"given":"Sai","family":"Ji","sequence":"first","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2891-4253","authenticated-orcid":false,"given":"Longkun","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Min","family":"Li","sequence":"additional","affiliation":[]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,4,15]]},"reference":[{"key":"569_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\u2013dual algorithms. In: Proceedings of the 58th annual IEEE symposium on foundations of computer science (FOCS), pp 61\u201372","DOI":"10.1109\/FOCS.2017.15"},{"issue":"2","key":"569_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 (2009) NP-hardness of Euclidean sum-of-squares clustering. Mach Learn 75(2):245\u2013248","journal-title":"Mach Learn"},{"key":"569_CR3","doi-asserted-by":"crossref","unstructured":"Arthur D, Vassilvitskii S (2006) How slow is the k-means method? In: Proceedings of the 22th symposium on computational geometry (SoCG), pp 144-153","DOI":"10.1145\/1137856.1137880"},{"key":"569_CR4","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: the advantages of careful seeding, In: Proceedings of the 18th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 1027\u20131035"},{"key":"569_CR5","unstructured":"Awasthi P, Charikar M, Krishnaswamy R, Sinop A (2015) The hardness of approximation of Euclidean $$k$$-means. In: Proceedings of the 31st symposium on computational geometry (SoCG), pp 754\u2013767"},{"key":"569_CR6","doi-asserted-by":"crossref","unstructured":"Bahmani B, Moseley B, Vattani A, Kumar R, Vassilvitskii S (2012) Scalable k-means++. Proc VLDB Endow 5(7):622\u2013633","DOI":"10.14778\/2180912.2180915"},{"key":"569_CR7","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer J, Lammersen C, Schmidt M, Sohler C (2016) Theoretical analysis of the k-means algorithm \u2013 a survey. In: Kliemann L, Sanders P (eds) Algorithm engineering. Lecture notes in computer science, vol 9220. Springer, Cham, pp 81\u2013116","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"569_CR8","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer J, Brauer S, Bujna K (2017) A theoretical analysis of the fuzzy $$k$$-means problem, In: Proceedings of the 16th IEEE international conference on data mining (ICDM), pp 805\u2013810","DOI":"10.1109\/ICDM.2016.0094"},{"issue":"2","key":"569_CR9","doi-asserted-by":"publisher","first-page":"644","DOI":"10.1137\/17M112717X","volume":"48","author":"V Cohen-Addad","year":"2019","unstructured":"Cohen-Addad V, Klein PN, Mathieu C (2019) Local search yields approximation schemes for $$k$$-means and $$k$$-median in Euclidean and minor-free metrics. SIAM J Comput 48(2):644\u2013667","journal-title":"SIAM J Comput"},{"issue":"1\u20132","key":"569_CR10","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1023\/A:1007612920971","volume":"42","author":"I Dhillon","year":"2001","unstructured":"Dhillon I, Modha D (2001) Concept decompositions for large sparse text data using clustering. Mach Learn 42(1\u20132):143\u2013175","journal-title":"Mach Learn"},{"issue":"1\u20133","key":"569_CR11","doi-asserted-by":"publisher","first-page":"9","DOI":"10.1023\/B:MACH.0000033113.59016.96","volume":"56","author":"P Drineas","year":"2004","unstructured":"Drineas P, Frieze A, Kannan R, Vempala V (2004) Clustering large graphs via the singular value decomposition. Mach Learn 56(1\u20133):9\u201333","journal-title":"Mach Learn"},{"key":"569_CR12","doi-asserted-by":"crossref","unstructured":"Endo Y, Miyamoto S (2015) Spherical $$k$$-means++ clustering. In: Proceedings of the 16th international conference on modeling decisions for artificial intelligence (MDAI), pp 103-114","DOI":"10.1007\/978-3-319-23240-9_9"},{"issue":"7","key":"569_CR13","doi-asserted-by":"publisher","first-page":"757","DOI":"10.14778\/3067421.3067425","volume":"10","author":"S Gupta","year":"2017","unstructured":"Gupta S, Kumar R, Lu K, Moseley B, Vassilvitskii S (2017) Local search methods for $$k$$-means with outliers. Proc VLDB Endow 10(7):757\u2013768","journal-title":"Proc VLDB Endow"},{"issue":"10","key":"569_CR14","first-page":"1","volume":"50","author":"K Hornik","year":"2015","unstructured":"Hornik K, Feinerer I, Kober M, Buchata M (2015) Spherical $$k$$-means clustering. J Stat Softw 50(10):1\u201322","journal-title":"J Stat Softw"},{"issue":"2\u20133","key":"569_CR15","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 D, Netanyahu N, Piatko C, Silverma R (2004) A local search approximation algorithm for $$k$$-means clustering. Comput Geom 28(2\u20133):89\u2013112","journal-title":"Comput Geom"},{"key":"569_CR16","doi-asserted-by":"crossref","unstructured":"Li M, Xu D, Zhang D, Zou J (2019) The seeding algorithms for spherical $$k$$-means clustering. J Glob Optim 76(4): 695\u2013708","DOI":"10.1007\/s10898-019-00779-w"},{"issue":"1","key":"569_CR17","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/s10878-019-00450-w","volume":"39","author":"M Li","year":"2020","unstructured":"Li M, Xu D, Yue J, Zhang D, Zhang P (2020) The seeding slgorithm for $$k$$-means problem with penalties. J Comb Optim 39(1):15\u201332","journal-title":"J Comb Optim"},{"issue":"2","key":"569_CR18","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(2):129\u2013137","journal-title":"IEEE Trans Inf Theory"},{"key":"569_CR19","doi-asserted-by":"crossref","unstructured":"Moriya T, Roth H, Nakamura S, Oda H, Kai N, Oda M (2018) Unsupervised pathology image segmentation using representation learning with spherical $$k$$-means. In: Proceeding SPIE 10581, Medical Imaging 2018: Digital Pathology, 1058111","DOI":"10.1117\/12.2292172"},{"issue":"1","key":"569_CR20","first-page":"12","volume":"13","author":"V Tunali","year":"2016","unstructured":"Tunali V, Bilgin T, Camurcu A (2016) An improved clustering algorithm for text mining: multi-cluster spherical $$K$$-means. Int Arab J Inf Technol 13(1):12\u201319","journal-title":"Int Arab J Inf Technol"},{"issue":"4","key":"569_CR21","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/s00454-011-9340-1","volume":"45","author":"A Vattani","year":"2011","unstructured":"Vattani A (2011) K-means requires exponentially many iterations even in the plane. Discrete Comput Geom 45(4):596\u2013616","journal-title":"Discrete Comput Geom"},{"key":"569_CR22","unstructured":"Xu J, Han J, Xiong K, Nie F (2016) Robust and sparse fuzzy $$k$$-means clustering. In: Proceedings 25th international joint conference on artificial intelligence (IJCAI), pp 2224\u20132230"},{"key":"569_CR23","first-page":"101","volume":"21","author":"D Xu","year":"2017","unstructured":"Xu D, Xu Y, Zhang D (2017) A survey on algorithm for $$k$$-means and its variants. Oper Res Trans 21:101\u2013109 (in Chinese)","journal-title":"Oper Res Trans"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00569-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00569-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00569-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:48:10Z","timestamp":1664354890000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00569-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,4,15]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["569"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00569-1","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,4,15]]},"assertion":[{"value":"15 April 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}