{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,18]],"date-time":"2025-10-18T00:02:22Z","timestamp":1760745742871,"version":"build-2065373602"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T00:00:00Z","timestamp":1756080000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T00:00:00Z","timestamp":1756080000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100004359","name":"Vetenskapsr\u00e5","doi-asserted-by":"publisher","award":["2022-03502","2020-03454"],"award-info":[{"award-number":["2022-03502","2020-03454"]}],"id":[{"id":"10.13039\/501100004359","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004270","name":"Royal Institute of Technology","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100004270","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2025,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Clustering is one of the most fundamental tools in data science and machine learning, and k-means clustering is one of the most common of such methods. There is a variety of approximate algorithms for the k-means problem, but only a few methods compute the globally optimal solution, as it is in general NP-hard. In this paper, we consider the k-means problem for instances with low-dimensional data and formulate it as a structured concave assignment problem. This allows us to exploit the low-dimensional structure and solve the problem to global optimality for very large data sets with several clusters, complementing and outperforming state-of-the-art for this class of problems. The method builds on iteratively solving a small concave problem and a large linear programming or assignment problem. This gives a sequence of feasible solutions along with bounds, which we show converges to a zero optimality gap. The paper combines methods from global optimization to accelerate the procedure, and we provide numerical results on synthetic data and real-world data.<\/jats:p>","DOI":"10.1007\/s11590-025-02235-z","type":"journal-article","created":{"date-parts":[[2025,8,25]],"date-time":"2025-08-25T15:38:09Z","timestamp":1756136289000},"page":"1539-1556","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A cutting plane algorithm for globally solving low-dimensional k-means problems"],"prefix":"10.1007","volume":"19","author":[{"given":"Martin","family":"Ryner","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0299-5745","authenticated-orcid":false,"given":"Jan","family":"Kronqvist","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Johan","family":"Karlsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,25]]},"reference":[{"key":"2235_CR1","unstructured":"MacQueen, J., et\u00a0al.: Some methods for classification and analysis of multivariate observations. In: Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, vol. 1, pp. 281\u2013297 (1967). Oakland, CA, USA"},{"issue":"2","key":"2235_CR2","doi-asserted-by":"crossref","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"},{"key":"2235_CR3","unstructured":"Arthur, D., Vassilvitskii, S.: K-means++ the advantages of careful seeding. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1027\u20131035 (2007)"},{"key":"2235_CR4","doi-asserted-by":"crossref","unstructured":"Kanungo, T., Mount, D.M., Netanyahu, N.S., Piatko, C.D., Silverman, R., Wu, A.Y.: A local search approximation algorithm for k-means clustering. In: Proceedings of the Eighteenth Annual Symposium on Computational Geometry, pp. 10\u201318 (2002)","DOI":"10.1145\/513400.513402"},{"issue":"4","key":"2235_CR5","doi-asserted-by":"crossref","first-page":"2144","DOI":"10.1287\/ijoc.2022.1166","volume":"34","author":"V Piccialli","year":"2022","unstructured":"Piccialli, V., Sudoso, A.M., Wiegele, A.: Sos-sdp: an exact solver for minimum sum-of-squares clustering. INFORMS J. Comput. 34(4), 2144\u20132162 (2022)","journal-title":"INFORMS J. Comput."},{"key":"2235_CR6","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s10898-010-9571-3","volume":"49","author":"D Aloise","year":"2011","unstructured":"Aloise, D., Hansen, P.: Evaluating a branch-and-bound rlt-based algorithm for minimum sum-of-squares clustering. J. Global Optim. 49, 449\u2013465 (2011)","journal-title":"J. Global Optim."},{"key":"2235_CR7","doi-asserted-by":"crossref","first-page":"195","DOI":"10.1007\/s10107-010-0349-7","volume":"131","author":"D Aloise","year":"2012","unstructured":"Aloise, D., Hansen, P., Liberti, L.: An improved column generation algorithm for minimum sum-of-squares clustering. Math. Program. 131, 195\u2013220 (2012)","journal-title":"Math. Program."},{"key":"2235_CR8","unstructured":"Hua, K., Shi, M., Cao, Y.: A scalable deterministic global optimization algorithm for clustering problems. In: International Conference on Machine Learning, pp. 4391\u20134401 (2021). PMLR"},{"key":"2235_CR9","doi-asserted-by":"crossref","unstructured":"Sculley, D.: Web-scale k-means clustering. In: Proceedings of the 19th International Conference on World Wide Web, pp. 1177\u20131178 (2010)","DOI":"10.1145\/1772690.1772862"},{"key":"2235_CR10","unstructured":"Elkan, C.: Using the triangle inequality to accelerate k-means. In: Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 147\u2013153 (2003)"},{"key":"2235_CR11","doi-asserted-by":"crossref","unstructured":"Aggarwal, A., Deshpande, A., Kannan, R.: Adaptive sampling for k-means clustering. In: International Workshop on Approximation Algorithms for Combinatorial Optimization, pp. 15\u201328 (2009). Springer","DOI":"10.1007\/978-3-642-03685-9_2"},{"issue":"1","key":"2235_CR12","doi-asserted-by":"crossref","first-page":"61","DOI":"10.1007\/s004540010019","volume":"24","author":"J Matou\u0161ek","year":"2000","unstructured":"Matou\u0161ek, J.: On approximate geometric k-clustering. Discr Comput Geomet 24(1), 61\u201384 (2000)","journal-title":"Discr Comput Geomet"},{"key":"2235_CR13","unstructured":"Lattanzi, S., Sohler, C.: A better k-means++ algorithm via local search. In: International Conference on Machine Learning, pp. 3662\u20133671 (2019). PMLR"},{"issue":"4","key":"2235_CR14","first-page":"17","volume":"49","author":"S Ahmadian","year":"2019","unstructured":"Ahmadian, S., Norouzi-Fard, A., Svensson, O., Ward, J.: Better guarantees for k-means and Euclidean k-median by primal-dual algorithms. SIAM J. Comput. 49(4), 17\u201397 (2019)","journal-title":"SIAM J. Comput."},{"key":"2235_CR15","doi-asserted-by":"crossref","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.: Improved and simplified inapproximability for k-means. Inf. Process. Lett. 120, 40\u201343 (2017)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"2235_CR16","doi-asserted-by":"crossref","first-page":"1485","DOI":"10.1137\/S1064827597328327","volume":"21","author":"O Du Merle","year":"1999","unstructured":"Du Merle, O., Hansen, P., Jaumard, B., Mladenovic, N.: An interior point algorithm for minimum sum-of-squares clustering. SIAM J. Sci. Comput. 21(4), 1485\u20131505 (1999)","journal-title":"SIAM J. Sci. Comput."},{"key":"2235_CR17","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1007\/s13675-017-0088-0","volume":"6","author":"DJ Papageorgiou","year":"2018","unstructured":"Papageorgiou, D.J., Trespalacios, F.: Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming. EURO J. Comput. Optim. 6, 55\u201383 (2018)","journal-title":"EURO J. Comput. Optim."},{"key":"2235_CR18","doi-asserted-by":"crossref","unstructured":"Kronqvist, J., Misener, R., Tsay, C.: P-split formulations: a class of intermediate formulations between big-m and convex hull for disjunctive constraints. Math. Program. pp. 1\u201338 (2025)","DOI":"10.1007\/s10107-025-02232-1"},{"issue":"1","key":"2235_CR19","doi-asserted-by":"crossref","first-page":"133","DOI":"10.1007\/s10898-022-01267-4","volume":"87","author":"JP Burgard","year":"2023","unstructured":"Burgard, J.P., Moreira Costa, C., Hojny, C., Kleinert, T., Schmidt, M.: Mixed-integer programming techniques for the minimum sum-of-squares clustering problem. J. Global Optim. 87(1), 133\u2013189 (2023)","journal-title":"J. Global Optim."},{"key":"2235_CR20","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"SP Boyd","year":"2004","unstructured":"Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"2235_CR21","first-page":"147","volume":"5","author":"G Birkhoff","year":"1946","unstructured":"Birkhoff, G.: Tres observaciones sobre el algebra lineal. Univ. Nac. Tucuman, Ser. A 5, 147\u2013154 (1946)","journal-title":"Univ. Nac. Tucuman, Ser. A"},{"key":"2235_CR22","first-page":"5","volume":"2","author":"J Von Neumann","year":"1953","unstructured":"Von Neumann, J.: A certain zero-sum two-person game equivalent to the optimal assignment problem. Contrib. Theory Games 2, 5\u201312 (1953)","journal-title":"Contrib. Theory Games"},{"key":"2235_CR23","unstructured":"Ryner, M., Kronqvist, J., Karlsson, J.: Globally solving the Gromov-Wasserstein problem for point clouds in low dimensional Euclidean spaces. In: Thirty-seventh Conference on Neural Information Processing Systems (2023)"},{"key":"2235_CR24","doi-asserted-by":"crossref","unstructured":"Walsh, T.: General symmetry breaking constraints. In: International Conference on Principles and Practice of Constraint Programming, pp. 650\u2013664 (2006). Springer","DOI":"10.1007\/11889205_46"},{"issue":"1\u20132","key":"2235_CR25","doi-asserted-by":"crossref","first-page":"197","DOI":"10.1007\/s10107-018-1239-7","volume":"175","author":"C Hojny","year":"2019","unstructured":"Hojny, C., Pfetsch, M.E.: Polytopes associated with symmetry handling. Math. Program. 175(1\u20132), 197\u2013240 (2019)","journal-title":"Math. Program."},{"key":"2235_CR26","doi-asserted-by":"publisher","unstructured":"Heinisch, P., Ostaszewski, K.: MatCL: A new easy-to use OpenCL toolbox for MathWorks Matlab. In: Proceedings of the International Workshop on OpenCL. IWOCL \u201918, May 2018, Oxford (United Kingdom), pp. 8\u2013181. ACM, New York, NY, USA (2018). https:\/\/doi.org\/10.1145\/3204919.3204927","DOI":"10.1145\/3204919.3204927"},{"key":"2235_CR27","unstructured":"Gurobi Optimization, LLC: Gurobi optimizer reference manual (2023). https:\/\/www.gurobi.com"},{"key":"2235_CR28","doi-asserted-by":"crossref","unstructured":"Bonneel, N., Van De\u00a0Panne, M., Paris, S., Heidrich, W.: Displacement interpolation using lagrangian mass transport. In: Proceedings of the 2011 SIGGRAPH Asia Conference, pp. 1\u201312 (2011)","DOI":"10.1145\/2024156.2024192"},{"key":"2235_CR29","unstructured":"Dua, D., Graff, C., et\u00a0al.: Uci machine learning repository, 2017. https:\/\/archive.ics.uci.edu\/ 7(1), 62 (2017)"},{"issue":"6","key":"2235_CR30","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1111\/1740-9713.01589","volume":"18","author":"A Unwin","year":"2021","unstructured":"Unwin, A., Kleinman, K.: The iris data set: in search of the source of virginica. Significance 18(6), 26\u201329 (2021)","journal-title":"Significance"},{"issue":"3","key":"2235_CR31","doi-asserted-by":"crossref","first-page":"188","DOI":"10.18201\/ijisae.2019355381","volume":"7","author":"I Cinar","year":"2019","unstructured":"Cinar, I., Koklu, M.: Classification of rice varieties using artificial intelligence methods. Int. J. Intell. Syst. Appl. Eng. 7(3), 188\u2013194 (2019)","journal-title":"Int. J. Intell. Syst. Appl. Eng."},{"key":"2235_CR32","doi-asserted-by":"publisher","unstructured":"Aeberhard, S., Forina, M.: Wine. UCI Machine learning repository. https:\/\/doi.org\/10.24432\/C5PC7J (1992)","DOI":"10.24432\/C5PC7J"},{"key":"2235_CR33","doi-asserted-by":"publisher","DOI":"10.24432\/C5J30W","author":"I-C Yeh","year":"2018","unstructured":"Yeh, I.-C.: Real estate valuation. UCI Mach. Learn. Repos. (2018). https:\/\/doi.org\/10.24432\/C5J30W","journal-title":"UCI Mach. Learn. Repos."},{"key":"2235_CR34","doi-asserted-by":"publisher","unstructured":"Matzka, S.: Explainable artificial intelligence for predictive maintenance applications. In: 2020 Third International Conference on Artificial Intelligence for Industries (AI4I), pp. 69\u201374 (2020). https:\/\/doi.org\/10.1109\/AI4I49448.2020.00023","DOI":"10.1109\/AI4I49448.2020.00023"},{"key":"2235_CR35","doi-asserted-by":"publisher","DOI":"10.24432\/C54G67","author":"RS Forsyth","year":"2016","unstructured":"Forsyth, R.S.: Liver disorders. UCI Mach. Learn. Repos. (2016). https:\/\/doi.org\/10.24432\/C54G67","journal-title":"UCI Mach. Learn. Repos."},{"issue":"3","key":"2235_CR36","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/S0020-0255(70)80056-1","volume":"2","author":"EH Ruspini","year":"1970","unstructured":"Ruspini, E.H.: Numerical methods for fuzzy clustering. Inf. Sci. 2(3), 319\u2013350 (1970)","journal-title":"Inf. Sci."},{"issue":"1","key":"2235_CR37","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1007\/BF01586932","volume":"51","author":"M Gr\u00f6tschel","year":"1991","unstructured":"Gr\u00f6tschel, M., Holland, O.: Solution of large-scale symmetric travelling salesman problems. Math. Program. 51(1), 141\u2013202 (1991)","journal-title":"Math. Program."}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02235-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-025-02235-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-025-02235-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,17]],"date-time":"2025-10-17T00:02:51Z","timestamp":1760659371000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-025-02235-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,25]]},"references-count":37,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2025,11]]}},"alternative-id":["2235"],"URL":"https:\/\/doi.org\/10.1007\/s11590-025-02235-z","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"type":"print","value":"1862-4472"},{"type":"electronic","value":"1862-4480"}],"subject":[],"published":{"date-parts":[[2025,8,25]]},"assertion":[{"value":"6 February 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"25 August 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no Conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}