{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T16:25:30Z","timestamp":1770567930748,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"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-00537-9","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T18:03:06Z","timestamp":1581530586000},"page":"1693-1704","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["The bi-criteria seeding algorithms for two variants of k-means problem"],"prefix":"10.1007","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-2784-5073","authenticated-orcid":false,"given":"Min","family":"Li","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,12]]},"reference":[{"key":"537_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":"537_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-dual algorithms. In: Proceedings of FOCS, pp 61\u201372","DOI":"10.1109\/FOCS.2017.15"},{"key":"537_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":"537_CR4","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: the advantages of careful seeding. In: Proceedings of SODA, pp 1027\u20131035"},{"key":"537_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":"537_CR6","doi-asserted-by":"crossref","unstructured":"Bachem O, Lucic M, Hassani SH, Krause A (2016) Approximate $$k$$-means++ in sublinear time. In: Proceedings of AAAI, pp 1459\u20131467","DOI":"10.1609\/aaai.v30i1.10259"},{"key":"537_CR7","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":"537_CR8","doi-asserted-by":"crossref","unstructured":"Bl\u00f6mer J, Lammersen C, Schmidt M, Sohler C (2016) Theoretical analysis of the $$k$$-means algorithm\u2014a survey. In: Algorithm engineering. Springer, pp 81\u2013116","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"537_CR9","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":"537_CR10","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":"537_CR11","doi-asserted-by":"crossref","unstructured":"Endo Y, Miyamoto S (2015) Spherical $$k$$-means++ clustering. In: Proceedings of MDAI, pp 103\u2013114","DOI":"10.1007\/978-3-319-23240-9_9"},{"key":"537_CR12","doi-asserted-by":"crossref","unstructured":"Feng Q, Zhang Z, Shi F, Wang J (2019) An improved approximation algorithm for the $$k$$-means problem with penalties. In: Proceedings of FAW, pp 170\u2013181","DOI":"10.1007\/978-3-030-18126-0_15"},{"key":"537_CR13","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":"537_CR14","doi-asserted-by":"publisher","DOI":"10.1007\/s10898-019-00779-w","author":"M Li","year":"2019","unstructured":"Li M, Xu D, Zhang D, Zou J (2019) The seeding algorithms for spherical $$k$$-means clustering. J Glob Optim. https:\/\/doi.org\/10.1007\/s10898-019-00779-w","journal-title":"J Glob Optim"},{"key":"537_CR15","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 algorithm for $$k$$-means problem with penalties. J Comb Optim 39:15\u201332","journal-title":"J Comb Optim"},{"key":"537_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":"537_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\/RONDOM, pp 14:1\u201314:20","DOI":"10.19086\/da.876"},{"key":"537_CR18","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":"537_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":"537_CR20","unstructured":"Wei D (2016) A constant-factor bi-criteria approximation guarantee for $$k$$-means++. In: Proceedings of NIPS, pp 604\u2013612"},{"key":"537_CR21","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s10115-007-0114-2","volume":"14","author":"X Wu","year":"2008","unstructured":"Wu X, Kumar V, Quinlan J, Ross Ghosh J, Yang Q, Motoda H, McLachlan GJ, Ng A, Liu B, Yu PS, Zhou Z, Steinbach M, Hand DJ, Steinberg D (2008) Top 10 algorithms in data mining. Knowl Inf Syst 14:1\u201337","journal-title":"Knowl Inf Syst"},{"key":"537_CR22","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1016\/j.knosys.2018.05.034","volume":"158","author":"X Xu","year":"2018","unstructured":"Xu X, Ding S, Shi Z (2018) An improved density peaks clustering algorithm with fast finding cluster centers. Knowl Based Syst 158:65\u201374","journal-title":"Knowl Based Syst"},{"key":"537_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 problem and its variants. Oper Res Trans 21:101\u2013109","journal-title":"Oper Res Trans"},{"key":"537_CR24","first-page":"31","volume":"22","author":"D Xu","year":"2018","unstructured":"Xu D, Xu Y, Zhang D (2018) A survey on the initialization methods for the $$k$$-means algorithm. Oper Res Trans 22:31\u201340","journal-title":"Oper Res Trans"},{"key":"537_CR25","doi-asserted-by":"crossref","unstructured":"Zhang D, Cheng Y, Li M, Wang Y, Xu D (2019) Local search approximation algorithms for the spherical $$k$$-means problem. In: Proceedings of AAIM, pp 341\u2013351","DOI":"10.1007\/978-3-030-27195-4_31"},{"key":"537_CR26","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s10878-018-0278-6","volume":"37","author":"D Zhang","year":"2018","unstructured":"Zhang D, Hao C, Wu C, Xu D, Zhang Z (2018) A local search approximation algorithm for the $$k$$-means problem with penalties. J Comb Optim 37:439\u2013453","journal-title":"J Comb Optim"},{"key":"537_CR27","unstructured":"Zhao Y, Karypis G (2001) Criterion functions for document clustering: experiments and analysis. Technical report $$\\sharp $$01-40, Department of Computer Science, University of Minnesota"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00537-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00537-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00537-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:45:48Z","timestamp":1664354748000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00537-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,12]]},"references-count":27,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["537"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00537-9","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,12]]},"assertion":[{"value":"12 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}