{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:20:18Z","timestamp":1740122418067,"version":"3.37.3"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T00:00:00Z","timestamp":1582588800000},"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"],"award-info":[{"award-number":["11531014"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000038","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["06446"],"award-info":[{"award-number":["06446"]}],"id":[{"id":"10.13039\/501100000038","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["11771386","11728104"],"award-info":[{"award-number":["11771386","11728104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"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"}]}],"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-00550-y","type":"journal-article","created":{"date-parts":[[2020,2,25]],"date-time":"2020-02-25T08:02:36Z","timestamp":1582617756000},"page":"1812-1823","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An approximation algorithm for the uniform capacitated k-means problem"],"prefix":"10.1007","volume":"44","author":[{"given":"Lu","family":"Han","sequence":"first","affiliation":[]},{"given":"Dachuan","family":"Xu","sequence":"additional","affiliation":[]},{"given":"Donglei","family":"Du","sequence":"additional","affiliation":[]},{"given":"Dongmei","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,25]]},"reference":[{"key":"550_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-28","DOI":"10.1007\/978-3-642-03685-9_2"},{"key":"550_CR2","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1007\/s10107-012-0565-4","volume":"141","author":"A Aggarwal","year":"2013","unstructured":"Aggarwal A, Louis A, Bansal M, Garg N, Gupta N, Gupta S, Jain S (2013) A $$3$$-approximation algorithm for the facility location problem with uniform capacities. Math Program 141:527\u2013547","journal-title":"Math Program"},{"key":"550_CR3","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":"550_CR4","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":"550_CR5","doi-asserted-by":"crossref","unstructured":"Arthur D, Vassilvitskii S (2006) How slow is the $$k$$-means method? In: Proceedings of SoCG, pp 144\u2013153","DOI":"10.1145\/1137856.1137880"},{"key":"550_CR6","unstructured":"Arthur D, Vassilvitskii S (2007) $$k$$-means++: the advantages of careful seeding. In: Proceedings of SODA, pp 1027\u20131035"},{"key":"550_CR7","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":"550_CR8","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":"550_CR9","unstructured":"Bachem O, Lucic M, Hassani SH, Krause A (2016) Fast and provably good seedings for $$k$$-means. In: Proceedings of NIPS, pp 55\u201363"},{"key":"550_CR10","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":"550_CR11","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":"550_CR12","doi-asserted-by":"publisher","first-page":"93","DOI":"10.1007\/s00224-017-9820-7","volume":"62","author":"A Bhattacharya","year":"2018","unstructured":"Bhattacharya A, Jaiswal R, Kumar A (2018) Faster algorithms for the constrained $$k$$-means problem. Theory Comput Syst 62:93\u2013115","journal-title":"Theory Comput Syst"},{"key":"550_CR13","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, pp 81\u2013116","DOI":"10.1007\/978-3-319-49487-6_3"},{"key":"550_CR14","doi-asserted-by":"crossref","unstructured":"Byrka J, Fleszar K, Rybicki B, Spoerhase J (2015) Bi-factor approximation algorithms for hard capacitated $$k$$-median problems. In: Proceedings of SODA, pp 722\u2013736","DOI":"10.1137\/1.9781611973730.49"},{"key":"550_CR15","doi-asserted-by":"crossref","unstructured":"Byrka J, Rybicki B, Uniyal S (2016) An approximation algorithm for uniform capacitated $$k$$-median problem with $$1+\\varepsilon $$ capacity violation. In: Proceedings of IPCO, pp 262\u2013274","DOI":"10.1007\/978-3-319-33461-5_22"},{"key":"550_CR16","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/s10107-004-0524-9","volume":"102","author":"FA Chudak","year":"2005","unstructured":"Chudak FA, Williamson DP (2005) Improved approximation algorithms for capacitated facility location problems. Math Program 102:207\u2013222","journal-title":"Math Program"},{"key":"550_CR17","unstructured":"Demirci G, Li S (2016) Constant approximation for capacitated $$k$$-median with $$(1+\\epsilon ) $$-capacity violation. In: Proceedings of ICALP, pp 73:1\u201373:14"},{"key":"550_CR18","doi-asserted-by":"crossref","unstructured":"Ding H, Xu J (2015) A unified framework for clustering constrained data without locality property. In: Proceedings of ACM-SIAM symposium on Discrete algorithms, pp 1471\u20131490","DOI":"10.1137\/1.9781611973730.97"},{"key":"550_CR19","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":"550_CR20","doi-asserted-by":"crossref","unstructured":"Feldman D, Monemizadeh M, Sohler C (2007) A PTAS for $$k$$-means clustering based on weak coresets. In: Proceedings of SoCG, pp 11\u201318","DOI":"10.1145\/1247069.1247072"},{"key":"550_CR21","doi-asserted-by":"publisher","first-page":"972","DOI":"10.1126\/science.1136800","volume":"315","author":"BJ Frey","year":"2007","unstructured":"Frey BJ, Dueck D (2007) Clustering by passing messages between data points. Science 315:972\u2013976","journal-title":"Science"},{"key":"550_CR22","first-page":"52","volume":"8","author":"S Geetha","year":"2009","unstructured":"Geetha S, Poonthalir G, Vanathi PT (2009) Improved $$k$$-means algorithm for capacitated clustering problem. J Comput Sci 8:52\u201359","journal-title":"J Comput Sci"},{"key":"550_CR23","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":"550_CR24","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 28:89\u2013112","journal-title":"Comput Geom"},{"key":"550_CR25","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1006\/jagm.2000.1100","volume":"37","author":"MR Korupolu","year":"2000","unstructured":"Korupolu MR, Plaxton CG, Rajaraman R (2000) Analysis of a local search heuristic for facility location problems. J Algorithms 37:146\u2013188","journal-title":"J Algorithms"},{"key":"550_CR26","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1016\/0191-2615(92)90032-R","volume":"26","author":"YA Koskosidis","year":"1992","unstructured":"Koskosidis YA, Powell WB (1992) Clustering algorithms for consolidation of customer orders into vehicle shipments. Transp Res Part B Methodol 26:365\u2013379","journal-title":"Transp Res Part B Methodol"},{"key":"550_CR27","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":"550_CR28","doi-asserted-by":"crossref","unstructured":"Li S (2015) On uniform capacitated $$k$$-median beyond the natural LP relaxation. In: Proceedings of SODA, pp 696\u2013707","DOI":"10.1137\/1.9781611973730.47"},{"key":"550_CR29","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":"550_CR30","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1016\/0377-2217(84)90155-3","volume":"18","author":"JM Mulvey","year":"1984","unstructured":"Mulvey JM, Beck MP (1984) Solving capacitated clustering problems. Eur J Oper Res 18:339\u2013348","journal-title":"Eur J Oper Res"},{"key":"550_CR31","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1016\/0969-6016(94)90032-9","volume":"1","author":"IH Osman","year":"1994","unstructured":"Osman IH, Christofides N (1994) Capacitated clustering problems by hybrid simulated annealing and tabu search. Int Trans Oper Res 1:317\u2013336","journal-title":"Int Trans Oper Res"},{"key":"550_CR32","doi-asserted-by":"crossref","unstructured":"Ostrovsky R, Rabani Y, Schulman LJ, Swamy C (2006) The effectiveness of Lloyd-type methods for the $$k$$-means problem. In: Proceedings of FOCS, pp 165\u2013176","DOI":"10.1109\/FOCS.2006.75"},{"key":"550_CR33","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1007\/s40305-013-0020-0","volume":"1","author":"J Shao","year":"2013","unstructured":"Shao J, Xu D (2013) An approximation algorithm for the risk-adjusted two-stage stochastic facility location problem with penalties. J Oper Res Soc China 1:339\u2013346","journal-title":"J Oper Res Soc China"},{"key":"550_CR34","first-page":"1","volume":"18","author":"HM Shieh","year":"2001","unstructured":"Shieh HM, May MD (2001) Solving the capacitated clustering problem with genetic algorithms. J Chin Inst Ind Eng 18:1\u201312","journal-title":"J Chin Inst Ind Eng"},{"key":"550_CR35","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. Discret Comput Geom 45:596\u2013616","journal-title":"Discret Comput Geom"},{"key":"550_CR36","doi-asserted-by":"publisher","first-page":"511","DOI":"10.1007\/s40305-013-0034-7","volume":"1","author":"C Wu","year":"2013","unstructured":"Wu C, Xu D, Shu J (2013) An approximation algorithm for the stochastic fault-tolerant facility location problem. J Oper Res Soc China 1:511\u2013522","journal-title":"J Oper Res Soc China"},{"key":"550_CR37","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1287\/moor.1040.0125","volume":"30","author":"J Zhang","year":"2005","unstructured":"Zhang J, Chen B, Ye Y (2005) A multiexchange local search algorithm for the capacitated facility location problem. Math Oper Res 30:389\u2013403","journal-title":"Math Oper Res"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00550-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-020-00550-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-020-00550-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,28]],"date-time":"2022-09-28T08:46:13Z","timestamp":1664354773000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-020-00550-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,25]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,10]]}},"alternative-id":["550"],"URL":"https:\/\/doi.org\/10.1007\/s10878-020-00550-y","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2020,2,25]]},"assertion":[{"value":"25 February 2020","order":1,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}