{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T14:05:34Z","timestamp":1781100334549,"version":"3.54.1"},"reference-count":19,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T00:00:00Z","timestamp":1690848000000},"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":["62202100"],"award-info":[{"award-number":["62202100"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2024,1]]},"DOI":"10.1007\/s00453-023-01158-4","type":"journal-article","created":{"date-parts":[[2023,8,1]],"date-time":"2023-08-01T13:02:23Z","timestamp":1690894943000},"page":"130-146","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":8,"title":["A Semi Brute-Force Search Approach for (Balanced) Clustering"],"prefix":"10.1007","volume":"86","author":[{"given":"Yicheng","family":"Xu","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vincent","family":"Chau","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Chenchen","family":"Wu","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yong","family":"Zhang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Vassilis","family":"Zissimopoulos","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Yifei","family":"Zou","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2023,8,1]]},"reference":[{"issue":"2","key":"1158_CR1","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"S Lloyd","year":"1982","unstructured":"Lloyd, S.: Least squares quantization in pcm. IEEE Trans. Inf. Theory 28(2), 129\u2013137 (1982)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"1158_CR2","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.R., Ghosh, J., Yang, Q., Motoda, H., McLachlan, G.J., Ng, A., Liu, B., Philip, S.Y., et al.: Top 10 algorithms in data mining. Knowl. Inf. Syst. 14(1), 1\u201337 (2008)","journal-title":"Knowl. Inf. Syst."},{"key":"1158_CR3","unstructured":"Arthur, D., Vassilvitskii, S.: $$k$$-means++: The advantages of careful seeding. In: Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1027\u20131035 (2007)"},{"key":"1158_CR4","doi-asserted-by":"crossref","unstructured":"Bahmani, B., Moseley, B., Vattani, A., Kumar, R., Vassilvitskii, S.: Scalable $$k$$-means++. In: Proceedings of the 38th Very Large Data Bases (VLDB), pp. 622\u2013633 (2012)","DOI":"10.14778\/2180912.2180915"},{"key":"1158_CR5","doi-asserted-by":"crossref","unstructured":"Bachem, O., Lucic, M., Hassani, S.H., Krause, A.: Approximate $$k$$-means++ in sublinear time. In: Proceedings of the 30th AAAI Conference on Artificial Intelligence (AAAI), pp. 1459\u20131467 (2016)","DOI":"10.1609\/aaai.v30i1.10259"},{"key":"1158_CR6","unstructured":"Lattanzi, S., Sohler, C.: A better $$k$$-means++ algorithm via local search. In: Proceedings of the 36th International Conference on Machine Learning (ICML), pp. 3662\u20133671 (2019)"},{"key":"1158_CR7","unstructured":"Choo, D., Grunau, C., Portmann, J., Rozho\u0148, V.: $$k$$-means++: few more steps yield constant approximation. In: Proceedings of the 37th International Conference on Machine Learning (ICML), pp. 1909\u20131917 (2020)"},{"key":"1158_CR8","unstructured":"Awasthi, P., Charikar, M., Krishnaswamy, R., Sinop, A.K.: The hardness of approximation of euclidean $$k$$-means. In: Proceedings of the 31st ACM Symposium on International Symposium on Computational Geometry (SoCG), pp. 754\u2013767 (2015)"},{"key":"1158_CR9","doi-asserted-by":"crossref","unstructured":"Liu, H., Han, J., Nie, F., Li, X.: Balanced clustering with least square regression. In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 2231\u20132237 (2017)","DOI":"10.1609\/aaai.v31i1.10877"},{"key":"1158_CR10","doi-asserted-by":"crossref","unstructured":"Li, Z., Nie, F., Chang, X., Ma, Z., Yang, Y.: Balanced clustering via exclusive lasso: A pragmatic approach. In: Proceedings of the 32nd AAAI Conference on Artificial Intelligence (AAAI), pp. 3596\u20133603 (2018)","DOI":"10.1609\/aaai.v32i1.11702"},{"key":"1158_CR11","doi-asserted-by":"crossref","unstructured":"Lin, W., He, Z., Xiao, M.: Balanced clustering: A uniform model and fast algorithm. In: Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI), pp. 2987\u20132993 (2019)","DOI":"10.24963\/ijcai.2019\/414"},{"issue":"3","key":"1158_CR12","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, R.H., Xu, D., Zhang, Y., Zou, Y.: A constant fpt approximation algorithm for hard-capacitated $$k$$-means. Optim. Eng. 21(3), 709\u2013722 (2020)","journal-title":"Optim. Eng."},{"key":"1158_CR13","unstructured":"Cohen-Addad, V., Li, J.: On the fixed-parameter tractability of capacitated clustering. In: Proceedings of the 46th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 1\u201314 (2019)"},{"key":"1158_CR14","unstructured":"Bandyapadhyay, S., Lochet, W., Saurabh, S.: FPT constant-approximations for capacitated clustering to minimize the sum of cluster radii. To appear in the proceedings of the 39th International Symposium on Computational Geometry (SoCG), (2023)"},{"issue":"6","key":"1158_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/2395116.2395117","volume":"59","author":"R Ostrovsky","year":"2013","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L.J., Swamy, C.: The effectiveness of Lloyd-type methods for the $$k$$-means problem. J. ACM 59(6), 1\u201322 (2013)","journal-title":"J. ACM"},{"key":"1158_CR16","doi-asserted-by":"crossref","unstructured":"Braverman, V., Cohen-Addad, V., Jiang, H.C.S., Krauthgamer, R., Schwiegelshohn, C., Toftrup, M.B., Wu, X.: The power of uniform sampling for coresets. In: Proceedings of the 63rd Annual Symposium on Foundations of Computer Science (FOCS), pp. 462\u2013473 (2022)","DOI":"10.1109\/FOCS54457.2022.00051"},{"issue":"2","key":"1158_CR17","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1145\/375827.375845","volume":"48","author":"K Jain","year":"2001","unstructured":"Jain, K., Vazirani, V.V.: Approximation algorithms for metric facility location and $$k$$-median problems using the primal-dual schema and Lagrangian relaxation. J. ACM 48(2), 274\u2013296 (2001)","journal-title":"J. ACM"},{"key":"1158_CR18","doi-asserted-by":"crossref","unstructured":"Inaba, M., Katoh, N., Imai, H.: Applications of weighted voronoi diagrams and randomization to variance-based $$k$$-clustering. In: Proceedings of the 10th ACM Symposium International Symposium on Computational Geometry (SoCG), pp. 332\u2013339 (1994)","DOI":"10.1145\/177424.178042"},{"key":"1158_CR19","volume-title":"Network Flows - Theory, Algorithms and Applications","author":"RK Ahuja","year":"1993","unstructured":"Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network Flows - Theory, Algorithms and Applications. Prentice Hall, USA (1993)"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01158-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-023-01158-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-023-01158-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,1,3]],"date-time":"2024-01-03T17:03:12Z","timestamp":1704301392000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-023-01158-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,1]]},"references-count":19,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2024,1]]}},"alternative-id":["1158"],"URL":"https:\/\/doi.org\/10.1007\/s00453-023-01158-4","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,1]]},"assertion":[{"value":"28 March 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 July 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 August 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declaratrions"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}]}}