{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,3]],"date-time":"2025-08-03T04:25:41Z","timestamp":1754195141229,"version":"3.37.3"},"reference-count":28,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,1,1]],"date-time":"2023-01-01T00:00:00Z","timestamp":1672531200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62202161","62172446"],"award-info":[{"award-number":["62202161","62172446"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100012166","name":"National Key R &D Program of China","doi-asserted-by":"crossref","award":["2021YFC3300603"],"award-info":[{"award-number":["2021YFC3300603"]}],"id":[{"id":"10.13039\/501100012166","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2023,1]]},"DOI":"10.1007\/s10878-022-00980-w","type":"journal-article","created":{"date-parts":[[2023,1,8]],"date-time":"2023-01-08T07:02:15Z","timestamp":1673161335000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On parameterized approximation algorithms for balanced clustering"],"prefix":"10.1007","volume":"45","author":[{"given":"Xiangyan","family":"Kong","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2974-5781","authenticated-orcid":false,"given":"Zhen","family":"Zhang","sequence":"additional","affiliation":[]},{"given":"Qilong","family":"Feng","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,1,8]]},"reference":[{"key":"980_CR1","unstructured":"Adamczyk M, Byrka J, Marcinkowski J, Meesum SM, Wlodarczyk M (2019) Constant-factor FPT approximation for capacitated $$k$$-median. In: Proceedings of of 27th annual European symposium on algorithms (ESA), pp 1:1\u20131:14"},{"key":"980_CR2","doi-asserted-by":"crossref","unstructured":"Ahmadian S, Norouzi-Fard A, Svensson O, Ward J (2020) Better guarantees for $$k$$-means and Euclidean $$k$$-median by primal-dual algorithms. SIAM J Comput 49(4)","DOI":"10.1137\/18M1171321"},{"key":"980_CR3","doi-asserted-by":"crossref","unstructured":"Aydin K, Bateni M, Mirrokni VS (2016) Distributed balanced partitioning via linear embedding. In: Proceedings of 9th ACM international conference on web search and data mining (WSDM), pp 387\u2013396","DOI":"10.1145\/2835776.2835829"},{"key":"980_CR4","unstructured":"Bandyapadhyay S, Fomin FV, Simonov K (2021) On coresets for fair clustering in metric and Euclidean spaces and their applications. In: Proceedings of 48th international colloquium on automata, languages, and programming (ICALP), pp 23:1\u201323:15"},{"key":"980_CR5","unstructured":"Bateni M, Bhaskara A, Lattanzi S, Mirrokni VS (2014) Distributed balanced clustering via mapping coresets. In: Proceedings of 27th annual conference on neural information processing systems (NeurIPS), pp 2591\u20132599"},{"issue":"2","key":"980_CR6","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1016\/j.ejor.2017.04.054","volume":"263","author":"S Borgwardt","year":"2017","unstructured":"Borgwardt S, Brieden A, Gritzmann P (2017) An LP-based $$k$$-means algorithm for balancing weighted point sets. Eur J Oper Res 263(2):349\u2013355","journal-title":"Eur J Oper Res"},{"issue":"2","key":"980_CR7","doi-asserted-by":"publisher","first-page":"23:1","DOI":"10.1145\/2981561","volume":"13","author":"J Byrka","year":"2017","unstructured":"Byrka J, Pensyl T, Rybicki B, Srinivasan A, Trinh K (2017) An improved approximation for $$k$$-median and positive correlation in budgeted optimization. ACM Trans Algorithms 13(2):23:1-23:31","journal-title":"ACM Trans Algorithms"},{"issue":"3","key":"980_CR8","doi-asserted-by":"publisher","first-page":"923","DOI":"10.1137\/070699007","volume":"39","author":"K Chen","year":"2009","unstructured":"Chen K (2009) On coresets for $$k$$-median and $$k$$-means clustering in metric and Euclidean spaces and their applications. SIAM J Comput 39(3):923\u2013947","journal-title":"SIAM J Comput"},{"key":"980_CR9","doi-asserted-by":"crossref","unstructured":"Cohen-Addad V, Esfandiari H, Mirrokni VS, Narayanan S (2022) Improved approximations for Euclidean $$k$$-means and $$k$$-median, via nested quasi-independent sets. In: Proceedings of 54th annual ACM SIGACT symposium on theory of computing (STOC). ACM, pp 1621\u20131628","DOI":"10.1145\/3519935.3520011"},{"key":"980_CR10","unstructured":"Cohen-Addad V, Gupta A, Kumar A, Lee E, Li J (2019) Tight FPT approximations for $$k$$-median and $$k$$-means. In: Proceedings of 46th international colloquium on automata, languages, and programming (ICALP), pp 42:1\u201342:14"},{"key":"980_CR11","unstructured":"Cohen-Addad V, Li J (2019) On the fixed-parameter tractability of capacitated clustering. In: Proceedings of 46th international colloquium on automata, languages, and programming (ICALP), pp 41:1\u201341:14"},{"key":"980_CR12","unstructured":"Demirci HG, Li S (2016) Constant approximation for capacitated $$k$$-median with $$(1+\\epsilon )$$-capacity violation. In: Proceedings of 43rd international colloquium on automata, languages, and programming (ICALP), pp 73:1\u201373:14"},{"key":"980_CR13","unstructured":"Dick T, Li M, Pillutla VK, White C, Balcan N, Smola AJ (2017) Data driven resource allocation for distributed learning. In: Proceedings of 20th international conference on artificial intelligence and statistics (AISTATS), pp 662\u2013671"},{"key":"980_CR14","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1016\/j.tcs.2020.07.022","volume":"842","author":"H Ding","year":"2020","unstructured":"Ding H (2020) Faster balanced clusterings in high dimension. Theor Comput Sci 842:28\u201340","journal-title":"Theor Comput Sci"},{"key":"980_CR15","unstructured":"Feng Q, Zhang Z, Huang Z, Xu J, Wang J (2020) A unified framework of FPT approximation algorithms for clustering problems. In: Proceedings of 31st international symposium on algorithms and computation (ISAAC), pp 5:1\u20135:17"},{"issue":"1","key":"980_CR16","doi-asserted-by":"publisher","first-page":"228","DOI":"10.1006\/jagm.1998.0993","volume":"31","author":"S Guha","year":"1999","unstructured":"Guha S, Khuller S (1999) Greedy strikes back: improved facility location algorithms. J Algorithms 31(1):228\u2013248","journal-title":"J Algorithms"},{"key":"980_CR17","doi-asserted-by":"crossref","unstructured":"Han L, Hao C, Wu C, Zhang Z (2020) Approximation algorithms for the lower-bounded $$k$$-median and its generalizations. In: Proceedings of 26th international conference on computing and combinatorics (COCOON), pp 627\u2013639","DOI":"10.1007\/978-3-030-58150-3_51"},{"key":"980_CR18","doi-asserted-by":"crossref","unstructured":"Li S (2016) Approximating capacitated $$k$$-median with $$(1+\\epsilon )k$$ open facilities. In: Proceedings of 27th annual ACM-SIAM symposium on discrete algorithms (SODA), pp 786\u2013796","DOI":"10.1137\/1.9781611974331.ch56"},{"issue":"2","key":"980_CR19","doi-asserted-by":"publisher","first-page":"22:1","DOI":"10.1145\/2983633","volume":"13","author":"S Li","year":"2017","unstructured":"Li S (2017) On uniform capacitated $$k$$-median beyond the natural LP relaxation. ACM Trans Algorithms 13(2):22:1-22:18","journal-title":"ACM Trans Algorithms"},{"issue":"2","key":"980_CR20","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1137\/130938645","volume":"45","author":"S Li","year":"2016","unstructured":"Li S, Svensson O (2016) Approximating $$k$$-median via pseudo-approximation. SIAM J Comput 45(2):530\u2013547","journal-title":"SIAM J Comput"},{"key":"980_CR21","doi-asserted-by":"crossref","unstructured":"Lin W, He Z, Xiao M (2019) Balanced clustering: A uniform model and fast algorithm. In: Proceedings of 28th international joint conference on artificial intelligence (IJCAI), pp 2987\u20132993","DOI":"10.24963\/ijcai.2019\/414"},{"key":"980_CR22","unstructured":"Manurangsi P, Raghavendra P (2017) A birthday repetition theorem and complexity of approximating dense CSPs. In: Proceedings of 44th international colloquium on automata, languages, and programming (ICALP), pp 78:1\u201378:15"},{"key":"980_CR23","doi-asserted-by":"publisher","first-page":"354","DOI":"10.1016\/j.ins.2018.11.030","volume":"480","author":"L Qi","year":"2019","unstructured":"Qi L, Wang R, Hu C, Li S, He Q, Xu X (2019) Time-aware distributed service recommendation with privacy-preservation. Inf Sci 480:354\u2013364","journal-title":"Inf Sci"},{"issue":"3","key":"980_CR24","doi-asserted-by":"publisher","first-page":"67","DOI":"10.1049\/iet-wss.2015.0069","volume":"6","author":"S Siavoshi","year":"2016","unstructured":"Siavoshi S, Kavian YS, Sharif H (2016) Load-balanced energy efficient clustering protocol for wireless sensor networks. IET Wirel Sens Syst 6(3):67\u201373","journal-title":"IET Wirel Sens Syst"},{"key":"980_CR25","doi-asserted-by":"crossref","unstructured":"Wu X, Shi F, Guo Y, Zhang Z, Huang J, Wang J (2022) An approximation algorithm for lower-bounded $$k$$-median with constant factor. Sci China Inf Sci 65(4):140601:1\u2013140601:9","DOI":"10.1007\/s11432-021-3411-7"},{"key":"980_CR26","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1016\/j.ins.2018.10.058","volume":"477","author":"X Xu","year":"2019","unstructured":"Xu X, Du Z, Chen X, Cai C (2019) Confidence consensus-based model for large-scale group decision making: a novel approach to managing non-cooperative behaviors. Inf Sci 477:410\u2013427","journal-title":"Inf Sci"},{"issue":"3","key":"980_CR27","doi-asserted-by":"publisher","first-page":"709","DOI":"10.1007\/s11081-020-09503-0","volume":"21","author":"Y Xu","year":"2020","unstructured":"Xu Y, M\u00f6hring RH, Xu D, Zhang Y, Zou Y (2020) A constant FPT approximation algorithm for hard-capacitated $$k$$-means. Optim Eng 21(3):709\u2013722","journal-title":"Optim Eng"},{"issue":"1","key":"980_CR28","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1109\/JIOT.2018.2842766","volume":"6","author":"D Zhang","year":"2019","unstructured":"Zhang D, Qiao Y, She L, Shen R, Ren J, Zhang Y (2019) Two time-scale resource management for green internet of things networks. IEEE Internet Things J 6(1):545\u2013556","journal-title":"IEEE Internet Things J"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00980-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-022-00980-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-022-00980-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,4]],"date-time":"2023-02-04T07:52:28Z","timestamp":1675497148000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-022-00980-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,1]]}},"alternative-id":["980"],"URL":"https:\/\/doi.org\/10.1007\/s10878-022-00980-w","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"type":"print","value":"1382-6905"},{"type":"electronic","value":"1573-2886"}],"subject":[],"published":{"date-parts":[[2023,1]]},"assertion":[{"value":"30 December 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"8 January 2023","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have not disclosed any competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"49"}}