{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,22]],"date-time":"2026-04-22T18:18:05Z","timestamp":1776881885772,"version":"3.51.2"},"reference-count":58,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T00:00:00Z","timestamp":1697068800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Universit\u00e0 degli Studi di Roma La Sapienza"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,5]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>The minimum sum-of-squares clustering (MSSC), or k-means type clustering, has been recently extended to exploit prior knowledge on the cardinality of each cluster. Such knowledge is used to increase performance as well as solution quality. In this paper, we propose a global optimization approach based on the branch-and-cut technique to solve the cardinality-constrained MSSC. For the lower bound routine, we use the semidefinite programming (SDP) relaxation recently proposed by Rujeerapaiboon et al. (SIAM J Optim 29(2):1211\u20131239, 2019). However, this relaxation can be used in a branch-and-cut method only for small-size instances. Therefore, we derive a new SDP relaxation that scales better with the instance size and the number of clusters. In both cases, we strengthen the bound by adding polyhedral cuts. Benefiting from a tailored branching strategy which enforces pairwise constraints, we reduce the complexity of the problems arising in the children nodes. For the upper bound, instead, we present a local search procedure that exploits the solution of the SDP relaxation solved at each node. Computational results show that the proposed algorithm globally solves, for the first time, real-world instances of size 10 times larger than those solved by state-of-the-art exact methods.<\/jats:p>","DOI":"10.1007\/s10107-023-02021-8","type":"journal-article","created":{"date-parts":[[2023,10,12]],"date-time":"2023-10-12T12:02:33Z","timestamp":1697112153000},"page":"245-279","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Global optimization for cardinality-constrained minimum sum-of-squares clustering via semidefinite programming"],"prefix":"10.1007","volume":"211","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3357-9608","authenticated-orcid":false,"given":"Veronica","family":"Piccialli","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2936-9931","authenticated-orcid":false,"given":"Antonio M.","family":"Sudoso","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2023,10,12]]},"reference":[{"issue":"335","key":"2021_CR1","doi-asserted-by":"crossref","first-page":"622","DOI":"10.1080\/01621459.1971.10482319","volume":"66","author":"M Rao","year":"1971","unstructured":"Rao, M.: Cluster analysis and mathematical programming. J. Am. Stat. Assoc. 66(335), 622\u2013626 (1971)","journal-title":"J. Am. Stat. Assoc."},{"key":"2021_CR2","volume-title":"Data Clustering: Theory, Algorithms, and Applications","author":"G Gan","year":"2020","unstructured":"Gan, G., Ma, C., Wu, J.: Data Clustering: Theory, Algorithms, and Applications, 2nd edn. Society for Industrial and Applied Mathematics, Philadelphia (2020)","edition":"2"},{"key":"2021_CR3","doi-asserted-by":"crossref","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.: NP-hardness of Euclidean sum-of-squares clustering. Mach. Learn. 75, 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"issue":"2","key":"2021_CR4","doi-asserted-by":"crossref","first-page":"1211","DOI":"10.1137\/17M1150670","volume":"29","author":"N Rujeerapaiboon","year":"2019","unstructured":"Rujeerapaiboon, N., Schindler, K., Kuhn, D., Wiesemann, W.: Size matters: Cardinality-constrained clustering and outlier detection via conic optimization. SIAM J. Optim. 29(2), 1211\u20131239 (2019)","journal-title":"SIAM J. Optim."},{"issue":"1\u201341","key":"2021_CR5","first-page":"2","volume":"1","author":"I Davidson","year":"2007","unstructured":"Davidson, I., Basu, S.: A survey of clustering with instance level constraints. ACM Trans. Knowl. Discov. Data. 1(1\u201341), 2\u201342 (2007)","journal-title":"ACM Trans. Knowl. Discov. Data."},{"key":"2021_CR6","unstructured":"Wagstaff, K., Cardie, C., Rogers, S., Schroedl, S., et al.: Constrained k-means clustering with background knowledge. In: ICML, vol. 1, pp. 577\u2013584 (2001)"},{"key":"2021_CR7","doi-asserted-by":"crossref","unstructured":"Baumann, P.: A binary linear programming-based k-means algorithm for clustering with must-link and cannot-link constraints. In: 2020 IEEE international conference on industrial engineering and engineering management (IEEM), pp. 324\u2013328. IEEE (2020)","DOI":"10.1109\/IEEM45057.2020.9309775"},{"issue":"3","key":"2021_CR8","doi-asserted-by":"crossref","first-page":"365","DOI":"10.1007\/s10618-006-0040-z","volume":"13","author":"A Banerjee","year":"2006","unstructured":"Banerjee, A., Ghosh, J.: Scalable clustering algorithms with balancing constraints. Data Min. Knowl. Discov. 13(3), 365\u2013395 (2006)","journal-title":"Data Min. Knowl. Discov."},{"issue":"8","key":"2021_CR9","doi-asserted-by":"crossref","first-page":"883","DOI":"10.1016\/j.knosys.2010.06.003","volume":"23","author":"S Zhu","year":"2010","unstructured":"Zhu, S., Wang, D., Li, T.: Data clustering with size constraints. Knowl.-Based Syst. 23(8), 883\u2013889 (2010)","journal-title":"Knowl.-Based Syst."},{"key":"2021_CR10","doi-asserted-by":"crossref","first-page":"105304","DOI":"10.1016\/j.cor.2021.105304","volume":"132","author":"M Gn\u00e4gi","year":"2021","unstructured":"Gn\u00e4gi, M., Baumann, P.: A matheuristic for large-scale capacitated clustering. Comput. Oper. Res. 132, 105304 (2021)","journal-title":"Comput. Oper. Res."},{"key":"2021_CR11","doi-asserted-by":"crossref","first-page":"115102","DOI":"10.1016\/j.eswa.2021.115102","volume":"182","author":"P Mancuso","year":"2021","unstructured":"Mancuso, P., Piccialli, V., Sudoso, A.M.: A machine learning approach for forecasting hierarchical time series. Expert Syst. Appl. 182, 115102 (2021)","journal-title":"Expert Syst. Appl."},{"issue":"4","key":"2021_CR12","doi-asserted-by":"crossref","first-page":"3301","DOI":"10.1109\/TSG.2022.3152147","volume":"13","author":"M Balletti","year":"2022","unstructured":"Balletti, M., Piccialli, V., Sudoso, A.M.: Mixed-integer nonlinear programming for state-based non-intrusive load monitoring. IEEE Trans. Smart Grid 13(4), 3301\u20133314 (2022)","journal-title":"IEEE Trans. Smart Grid"},{"issue":"4","key":"2021_CR13","doi-asserted-by":"crossref","first-page":"1397","DOI":"10.1016\/j.ipm.2008.03.001","volume":"44","author":"G Hu","year":"2008","unstructured":"Hu, G., Zhou, S., Guan, J., Hu, X.: Towards effective document clustering: A constrained k-means based approach. Inf. Process. Manag. 44(4), 1397\u20131409 (2008)","journal-title":"Inf. Process. Manag."},{"key":"2021_CR14","first-page":"447","volume-title":"Constrained Clustering: Current and New Trends","author":"P Gan\u00e7arski","year":"2020","unstructured":"Gan\u00e7arski, P., Dao, T.-B.-H., Cr\u00e9milleux, B., Forestier, G., Lampert, T.: Constrained Clustering: Current and New Trends, pp. 447\u2013484. Springer, Cham (2020)"},{"key":"2021_CR15","doi-asserted-by":"crossref","first-page":"83","DOI":"10.1007\/s10898-021-01047-6","volume":"83","author":"L Liberti","year":"2022","unstructured":"Liberti, L., Manca, B.: Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections. J. Global Optim. 83, 83\u2013118 (2022)","journal-title":"J. Global Optim."},{"issue":"6","key":"2021_CR16","doi-asserted-by":"crossref","first-page":"2341","DOI":"10.1007\/s10618-021-00794-0","volume":"35","author":"R Randel","year":"2021","unstructured":"Randel, R., Aloise, D., Blanchard, S.J., Hertz, A.: A Lagrangian-based score for assessing the quality of pairwise constraints in semi-supervised clustering. Data Min. Knowl. Discov. 35(6), 2341\u20132368 (2021)","journal-title":"Data Min. Knowl. Discov."},{"key":"2021_CR17","first-page":"0","volume":"20","author":"PS Bradley","year":"2000","unstructured":"Bradley, P.S., Bennett, K.P., Demiriz, A.: Constrained k-means clustering. Microsoft Res. Redmond 20, 0 (2000)","journal-title":"Microsoft Res. Redmond"},{"issue":"2","key":"2021_CR18","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":"2021_CR19","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1007\/978-3-662-44415-3_4","volume-title":"Structural, Syntactic, and Statistical Pattern Recognition","author":"MI Malinen","year":"2014","unstructured":"Malinen, M.I., Fr\u00e4nti, P.: Balanced k-means for clustering. In: Fr\u00e4nti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) Structural, Syntactic, and Statistical Pattern Recognition, pp. 32\u201341. Springer, Berlin, Heidelberg (2014)"},{"key":"2021_CR20","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1016\/j.ins.2017.06.019","volume":"415","author":"LR Costa","year":"2017","unstructured":"Costa, L.R., Aloise, D., Mladenovi\u0107, N.: Less is more: basic variable neighborhood search heuristic for balanced minimum sum-of-squares clustering. Inf. Sci. 415, 247\u2013253 (2017)","journal-title":"Inf. Sci."},{"issue":"3","key":"2021_CR21","doi-asserted-by":"crossref","first-page":"503","DOI":"10.1590\/S0101-74382009000300002","volume":"29","author":"D Aloise","year":"2009","unstructured":"Aloise, D., Hansen, P.: A branch-and-cut SDP-based algorithm for minimum sum-of-squares clustering. Pesqui. Oper. 29(3), 503\u2013516 (2009)","journal-title":"Pesqui. Oper."},{"issue":"1","key":"2021_CR22","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(1), 195\u2013220 (2012)","journal-title":"Math. Program."},{"key":"2021_CR23","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1016\/j.cor.2015.07.008","volume":"66","author":"N Krislock","year":"2016","unstructured":"Krislock, N., Malick, J., Roupin, F.: Computational results of a semidefinite branch-and-bound algorithm for k-cluster. Comput. Oper. Res. 66, 153\u2013159 (2016)","journal-title":"Comput. Oper. Res."},{"issue":"4","key":"2021_CR24","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."},{"issue":"2","key":"2021_CR25","doi-asserted-by":"crossref","first-page":"214","DOI":"10.1007\/s10618-008-0104-3","volume":"18","author":"Y Xia","year":"2009","unstructured":"Xia, Y.: A global optimization method for semi-supervised clustering. Data Min. Knowl. Discov. 18(2), 214\u2013256 (2009)","journal-title":"Data Min. Knowl. Discov."},{"key":"2021_CR26","doi-asserted-by":"crossref","unstructured":"Babaki, B., Guns, T., Nijssen, S.: Constrained clustering using column generation. In: International conference on AI and OR techniques in constriant programming for combinatorial optimization problems, pp. 438\u2013454 (2014). Springer","DOI":"10.1007\/978-3-319-07046-9_31"},{"key":"2021_CR27","doi-asserted-by":"crossref","first-page":"105958","DOI":"10.1016\/j.cor.2022.105958","volume":"147","author":"V Piccialli","year":"2022","unstructured":"Piccialli, V., Russo Russo, A., Sudoso, A.M.: An exact algorithm for semi-supervised minimum sum-of-squares clustering. Comput. Oper. Res. 147, 105958 (2022)","journal-title":"Comput. Oper. Res."},{"key":"2021_CR28","doi-asserted-by":"crossref","unstructured":"Dao, T.-B.-H., Duong, K.-C., Vrain, C.: A declarative framework for constrained clustering. In: Joint European conference on machine learning and knowledge discovery in databases, pp. 419\u2013434 (2013). Springer","DOI":"10.1007\/978-3-642-40994-3_27"},{"key":"2021_CR29","doi-asserted-by":"crossref","first-page":"70","DOI":"10.1016\/j.artint.2015.05.006","volume":"244","author":"T-B-H Dao","year":"2017","unstructured":"Dao, T.-B.-H., Duong, K.-C., Vrain, C.: Constrained clustering by constraint programming. Artif. Intell. 244, 70\u201394 (2017)","journal-title":"Artif. Intell."},{"key":"2021_CR30","unstructured":"Guns, T., Dao, T.-B.-H., Vrain, C., Duong, K.-C.: Repetitive branch-and-bound using constraint programming for constrained minimum sum-of-squares clustering. In: Proceedings of the Twenty-second european conference on artificial intelligence. ECAI\u201916, pp. 462\u2013470. IOS Press, NLD (2016)"},{"key":"2021_CR31","doi-asserted-by":"crossref","unstructured":"Haouas, M.N., Aloise, D., Pesant, G.: An exact CP approach for the cardinality-constrained Euclidean minimum sum-of-squares clustering problem. In: International conference on integration of constraint programming, artificial intelligence, and operations research, pp. 256\u2013272 (2020). Springer","DOI":"10.1007\/978-3-030-58942-4_17"},{"issue":"1","key":"2021_CR32","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1137\/1038003","volume":"38","author":"L Vandenberghe","year":"1996","unstructured":"Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49\u201395 (1996)","journal-title":"SIAM Rev."},{"issue":"1","key":"2021_CR33","doi-asserted-by":"crossref","first-page":"186","DOI":"10.1137\/050641983","volume":"18","author":"J Peng","year":"2007","unstructured":"Peng, J., Wei, Y.: Approximating k-means-type clustering via semidefinite programming. SIAM J. Optim. 18(1), 186\u2013205 (2007)","journal-title":"SIAM J. Optim."},{"key":"2021_CR34","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Bandeira, A.S., Charikar, M., Krishnaswamy, R., Villar, S., Ward, R.: Relax, no need to round: integrality of clustering formulations. In: Proceedings of the 2015 conference on innovations in theoretical computer science, pp. 191\u2013200 (2015)","DOI":"10.1145\/2688073.2688116"},{"issue":"2","key":"2021_CR35","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/s10107-016-1097-0","volume":"165","author":"T Iguchi","year":"2017","unstructured":"Iguchi, T., Mixon, D.G., Peterson, J., Villar, S.: Probably certifiably correct k-means clustering. Math. Program. 165(2), 605\u2013642 (2017)","journal-title":"Math. Program."},{"issue":"1","key":"2021_CR36","doi-asserted-by":"crossref","first-page":"295","DOI":"10.1007\/s10107-018-1333-x","volume":"179","author":"X Li","year":"2020","unstructured":"Li, X., Li, Y., Ling, S., Strohmer, T., Wei, K.: When do birds of a feather flock together? k-means, proximity, and conic programming. Math. Program. 179(1), 295\u2013341 (2020)","journal-title":"Math. Program."},{"issue":"1","key":"2021_CR37","doi-asserted-by":"crossref","first-page":"173","DOI":"10.1137\/20M1348601","volume":"32","author":"A De Rosa","year":"2022","unstructured":"De Rosa, A., Khajavirad, A.: The ratio-cut polytope and k-means clustering. SIAM J. Optim. 32(1), 173\u2013203 (2022)","journal-title":"SIAM J. Optim."},{"key":"2021_CR38","doi-asserted-by":"publisher","unstructured":"Krislock, N., Wolkowicz, H.: In: Anjos, M.F., Lasserre, J.B. (eds.) Euclidean Distance Matrices and Applications, pp. 879\u2013914. Springer, New York, NY (2012). https:\/\/doi.org\/10.1007\/978-1-4614-0769-0_30","DOI":"10.1007\/978-1-4614-0769-0_30"},{"key":"2021_CR39","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-97846-8","volume-title":"Euclidean Distance Matrices and Their Applications in Rigidity Theory","author":"AY Alfakih","year":"2018","unstructured":"Alfakih, A.Y.: Euclidean Distance Matrices and Their Applications in Rigidity Theory. Springer, NewYork (2018). https:\/\/doi.org\/10.1007\/978-3-319-97846-8"},{"issue":"6","key":"2021_CR40","doi-asserted-by":"crossref","first-page":"3408","DOI":"10.1137\/090748834","volume":"20","author":"H Mittelmann","year":"2010","unstructured":"Mittelmann, H., Peng, J.: Estimating bounds for quadratic assignment problems associated with hamming and manhattan distance matrices based on semidefinite programming. SIAM J. Optim. 20(6), 3408\u20133426 (2010)","journal-title":"SIAM J. Optim."},{"issue":"1","key":"2021_CR41","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1287\/moor.1100.0473","volume":"36","author":"Y Ding","year":"2011","unstructured":"Ding, Y., Ge, D., Wolkowicz, H.: On equivalence of semidefinite relaxations for quadratic matrix programming. Math. Oper. Res. 36(1), 88\u2013104 (2011)","journal-title":"Math. Oper. Res."},{"key":"2021_CR42","doi-asserted-by":"crossref","first-page":"461","DOI":"10.1016\/S0166-218X(99)00102-X","volume":"96","author":"H Wolkowicz","year":"1999","unstructured":"Wolkowicz, H., Zhao, Q.: Semidefinite programming relaxations for the graph partitioning problem. Discrete Appl. Math. 96, 461\u2013479 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"3","key":"2021_CR43","doi-asserted-by":"crossref","first-page":"853","DOI":"10.1007\/s10589-020-00261-4","volume":"78","author":"X Li","year":"2021","unstructured":"Li, X., Pong, T.K., Sun, H., Wolkowicz, H.: A strictly contractive Peaceman\u2013Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem. Comput. Optim. Appl. 78(3), 853\u2013891 (2021)","journal-title":"Comput. Optim. Appl."},{"issue":"1","key":"2021_CR44","doi-asserted-by":"crossref","first-page":"149","DOI":"10.1214\/17-AOS1545","volume":"46","author":"AA Amini","year":"2018","unstructured":"Amini, A.A., Levina, E.: On semidefinite relaxations for the block model. Ann. Statist. 46(1), 149\u2013179 (2018)","journal-title":"Ann. Statist."},{"key":"2021_CR45","unstructured":"MOSEK: The MOSEK Optimization Toolbox for MATLAB Manual. Version 9.3.21. (2022). http:\/\/docs.mosek.com\/9.3\/toolbox\/index.html"},{"issue":"1","key":"2021_CR46","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1137\/0805002","volume":"5","author":"F Alizadeh","year":"1995","unstructured":"Alizadeh, F.: Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5(1), 13\u201351 (1995)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2021_CR47","doi-asserted-by":"crossref","first-page":"203","DOI":"10.1007\/s12532-010-0017-1","volume":"2","author":"Z Wen","year":"2010","unstructured":"Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2(3), 203\u2013230 (2010)","journal-title":"Math. Program. Comput."},{"issue":"2","key":"2021_CR48","doi-asserted-by":"crossref","first-page":"882","DOI":"10.1137\/140964357","volume":"25","author":"D Sun","year":"2015","unstructured":"Sun, D., Toh, K.-C., Yang, L.: A convergent 3-block semiproximal alternating direction method of multipliers for conic programming with 4-type constraints. SIAM J. Optim. 25(2), 882\u2013915 (2015)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"2021_CR49","doi-asserted-by":"crossref","first-page":"331","DOI":"10.1007\/s12532-015-0082-6","volume":"7","author":"L Yang","year":"2015","unstructured":"Yang, L., Sun, D., Toh, K.-C.: SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints. Math. Program. Comput. 7(3), 331\u2013366 (2015)","journal-title":"Math. Program. Comput."},{"issue":"1","key":"2021_CR50","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1137\/050622870","volume":"46","author":"C Jansson","year":"2008","unstructured":"Jansson, C., Chaykin, D., Keil, C.: Rigorous error bounds for the optimal value in semidefinite programming. SIAM J. Numer. Anal. 46(1), 180\u2013200 (2008)","journal-title":"SIAM J. Numer. Anal."},{"issue":"3","key":"2021_CR51","doi-asserted-by":"crossref","first-page":"415","DOI":"10.1007\/s10288-020-00454-x","volume":"19","author":"M Cerulli","year":"2021","unstructured":"Cerulli, M., De Santis, M., Gaar, E., Wiegele, A.: Improving ADMMs for solving doubly nonnegative programs through dual factorization. 4OR 19(3), 415\u2013448 (2021)","journal-title":"4OR"},{"issue":"7","key":"2021_CR52","doi-asserted-by":"crossref","first-page":"1906","DOI":"10.1016\/j.laa.2012.04.038","volume":"437","author":"J-C Bourin","year":"2012","unstructured":"Bourin, J.-C., Lee, E.-Y., Lin, M.: On a decomposition lemma for positive semi-definite block-matrices. Linear Algebra Appl. 437(7), 1906\u20131912 (2012)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"2021_CR53","doi-asserted-by":"crossref","first-page":"139","DOI":"10.1007\/BF01589101","volume":"45","author":"M Padberg","year":"1989","unstructured":"Padberg, M.: The boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1), 139\u2013172 (1989)","journal-title":"Math. Program."},{"issue":"10","key":"2021_CR54","doi-asserted-by":"crossref","first-page":"1027","DOI":"10.1016\/S0167-8655(99)00069-0","volume":"20","author":"JM Pena","year":"1999","unstructured":"Pena, J.M., Lozano, J.A., Larranaga, P.: An empirical comparison of four initialization methods for the k-means algorithm. Pattern Recognit. Lett. 20(10), 1027\u20131040 (1999)","journal-title":"Pattern Recognit. Lett."},{"key":"2021_CR55","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1016\/j.patcog.2019.04.014","volume":"93","author":"P Fr\u00e4nti","year":"2019","unstructured":"Fr\u00e4nti, P., Sieranoja, S.: How much can k-means be improved by using better initialization and repeats? Pattern Recognit. 93, 95\u2013112 (2019)","journal-title":"Pattern Recognit."},{"issue":"1","key":"2021_CR56","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1080\/10556788.2019.1576176","volume":"35","author":"D Sun","year":"2020","unstructured":"Sun, D., Toh, K.-C., Yuan, Y., Zhao, X.-Y.: SDPNAL+: a Matlab software for semidefinite programming with bound constraints (version 1.0). Optim. Methods Softw. 35(1), 87\u2013115 (2020)","journal-title":"Optim. Methods Softw."},{"key":"2021_CR57","unstructured":"Gurobi: Gurobi Optimizer Reference Manual (2021). http:\/\/www.gurobi.com"},{"key":"2021_CR58","unstructured":"Chierichetti, F., Kumar, R., Lattanzi, S., Vassilvitskii, S.: Fair clustering through fairlets. Adv. Neural Inf. Process. Syst. 30 (2017)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02021-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-023-02021-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-023-02021-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,28]],"date-time":"2025-04-28T13:56:22Z","timestamp":1745848582000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-023-02021-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,10,12]]},"references-count":58,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,5]]}},"alternative-id":["2021"],"URL":"https:\/\/doi.org\/10.1007\/s10107-023-02021-8","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,10,12]]},"assertion":[{"value":"28 December 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 September 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 October 2023","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 have no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}