{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T21:04:34Z","timestamp":1781039074291,"version":"3.54.1"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T00:00:00Z","timestamp":1569456000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T00:00:00Z","timestamp":1569456000000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"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\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["11531014"],"award-info":[{"award-number":["11531014"]}],"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":["11626148"],"award-info":[{"award-number":["11626148"]}],"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":["11701342"],"award-info":[{"award-number":["11701342"]}],"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\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61672323"],"award-info":[{"award-number":["61672323"]}],"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":[[2020,1]]},"DOI":"10.1007\/s10878-019-00450-w","type":"journal-article","created":{"date-parts":[[2019,9,26]],"date-time":"2019-09-26T23:26:12Z","timestamp":1569540372000},"page":"15-32","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["The seeding algorithm for k-means problem with penalties"],"prefix":"10.1007","volume":"39","author":[{"given":"Min","family":"Li","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jun","family":"Yue","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peng","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2019,9,26]]},"reference":[{"key":"450_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal A, Deshpande A, Kannan R (2009) Adaptive sampling for $$k$$-means clustering. In: Proceedings of APPROX and RANDOM, pp. 15\u201328","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"450_CR2","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 FOCS, pp. 61\u201372","DOI":"10.1109\/FOCS.2017.15"},{"key":"450_CR3","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\u2013248","journal-title":"Mach Learn"},{"key":"450_CR4","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: The advantages of careful seeding. In: Proceedings of SODA, pp. 1027\u20131035"},{"key":"450_CR5","unstructured":"Awasthi P, Charikar M, Krishnaswamy R, Sinop AK (2015) The hardness of approximation of Euclidean $$k$$-means. In: Proceedings of SoCG, pp. 754\u2013767"},{"key":"450_CR6","doi-asserted-by":"crossref","unstructured":"Bachem O, Lucic M, Hassani SH, Krause A (2016a) Approximate $$k$$-means++ in sublinear time. In: Proceedings of AAAI, pp. 1459\u20131467","DOI":"10.1609\/aaai.v30i1.10259"},{"key":"450_CR7","unstructured":"Bachem O, Lucic M, Hassani SH, Krause A (2016b) Fast and provably good seedings for $$k$$-means. In: Proceedings of NIPS, pp. 55\u201363"},{"key":"450_CR8","unstructured":"Bachem O, Lucic M, Krause A (2017) Distributed and provably good seedings for $$k$$-means in constant rounds. In: Proceedings of ICML, pp. 292\u2013300"},{"key":"450_CR9","doi-asserted-by":"crossref","unstructured":"Bahmani B, Moseley B, Vattani A, Kumar R, Vassilvitskii S (2012) Scalable $$k$$-means++. In: Proceedings of the VLDB endowment, pp. 622\u2013633","DOI":"10.14778\/2180912.2180915"},{"key":"450_CR10","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer J, Lammersen C, Schmidt M, Sohler C (2016) Theoretical analysis of the $$k$$-means algorithm\u2013a survey. In: Kliemann L, Sanders P (eds) Algorithm engineering, Springer, New York, pp. 81\u2013116","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"450_CR11","unstructured":"Chang XY, Wang Y, Li R, Xu Z (2014) Sparse $$k$$-means with $$l_\\infty $$\/$$l_0$$ penalty for high-dimensional data clustering. arXiv:1403.7890v1"},{"key":"450_CR12","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 S, Vinay V (2004) Clustering large graphs via the singular value decomposition. Mach Learn 56:9\u201333","journal-title":"Mach Learn"},{"key":"450_CR13","unstructured":"Har-Peled S, Sadri B (2005) How fast is the $$k$$-means method? In: Proceedings of SODA, pp. 332\u2013229"},{"key":"450_CR14","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, Silverma 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":"450_CR15","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1016\/j.ipl.2016.11.009","volume":"120","author":"E Lee","year":"2017","unstructured":"Lee E, Schmidt M, Wright J (2017) Improved and simplified inapproximability for $$k$$-means. Inf Process Lett 120:40\u201343","journal-title":"Inf Process Lett"},{"key":"450_CR16","doi-asserted-by":"publisher","first-page":"21","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:21\u201333","journal-title":"IEEE Trans Inf Theory"},{"key":"450_CR17","doi-asserted-by":"publisher","first-page":"28:1","DOI":"10.1145\/2395116.2395117","volume":"59","author":"R Ostrovsky","year":"2012","unstructured":"Ostrovsky R, Rabani Y, Schulman L, Swamy C (2012) The effectiveness of Lloyd-type methods for the $$k$$-means problem. J ACM 59:28:1\u201328:22","journal-title":"J ACM"},{"key":"450_CR18","doi-asserted-by":"publisher","first-page":"2173","DOI":"10.1109\/TKDE.2016.2551240","volume":"28","author":"M Rezaei","year":"2016","unstructured":"Rezaei M, F\u00e4rnti P (2016) Set matching measures for external cluster validity. IEEE Trans Knowl Data Eng 28:2173\u20132186","journal-title":"IEEE Trans Knowl Data Eng"},{"key":"450_CR19","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 $$k$$-means for clustering with scattered objects and prior information in high-throughput biological data. Bioinformatics 23:2247\u20132255","journal-title":"Bioinformatics"},{"key":"450_CR20","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/s11248-011-9513-y","volume":"21","author":"D Xu","year":"2017","unstructured":"Xu D, Xu Y, Zhang D (2017) A survey on algorithm for $$k$$-means problem and its variants. Oper Res Trans 21:101\u2013109","journal-title":"Oper Res Trans"},{"key":"450_CR21","doi-asserted-by":"crossref","unstructured":"Zhang D, Hao C, Wu C, Xu D, Zhang Z (2017) A local search approximation algorithm for the $$k$$-means problem with penalties. In: Proceedings of COCOON, pp. 568\u2013574","DOI":"10.1007\/978-3-319-62389-4_47"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00450-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10878-019-00450-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-019-00450-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,30]],"date-time":"2022-09-30T01:21:48Z","timestamp":1664500908000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10878-019-00450-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,9,26]]},"references-count":21,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["450"],"URL":"https:\/\/doi.org\/10.1007\/s10878-019-00450-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,9,26]]},"assertion":[{"value":"26 September 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}