{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T19:34:14Z","timestamp":1787340854094,"version":"build-2736575974"},"reference-count":26,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1752125"],"award-info":[{"award-number":["1752125"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Optim."],"published-print":{"date-parts":[[2018,1]]},"abstract":"<jats:p>In this paper, we show that the popular $K$-means clustering problem can equivalently be reformulated as a conic program of polynomial size. The arising convex optimization problem is NP-hard, but amenable to a tractable semidefinite programming (SDP) relaxation that is tighter than the current SDP relaxation schemes in the literature. In contrast to the existing schemes, our proposed SDP formulation gives rise to solutions that can be leveraged to identify the clusters. We devise a new approximation algorithm for $K$-means clustering that utilizes the improved formulation and empirically illustrate its superiority over the state-of-the-art solution schemes.<\/jats:p>","DOI":"10.1137\/17m1135724","type":"journal-article","created":{"date-parts":[[2018,11,8]],"date-time":"2018-11-08T12:08:48Z","timestamp":1541678928000},"page":"3105-3126","source":"Crossref","is-referenced-by-count":9,"title":["Improved Conic Reformulations for $K$-means Clustering"],"prefix":"10.1137","volume":"28","author":[{"given":"Madhushini Narayana","family":"Prasad","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Grani A.","family":"Hanasusanto","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2018,11,8]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"P. A. Absil, R. Mahony, and R. Sepulchre,\n                      Optimization Algorithms on Matrix Manifolds\n                      , Princeton University Press, Princeton, NJ, 2009.","DOI":"10.1515\/9781400830244"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"atypb3","first-page":"1728","volume":"32","author":"Asteris M.","year":"2014","journal-title":"Proc. Mach. Learn. Res."},{"key":"atypb4","first-page":"191","author":"Awasthi P.","year":"2015","journal-title":"New York"},{"key":"atypb5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020209017701"},{"key":"atypb6","doi-asserted-by":"crossref","unstructured":"S. Burer,\n                      Copositive programming\n                      , in Handbook on Semidefinite, Conic and Polynomial Optimization, Internat. Ser. Oper. Res. Manag. Sci. 166, M. F. Anjos and J. B. Lasserre, eds., Springer, New York, 2012, pp. 201-218.","DOI":"10.1007\/978-1-4614-0769-0_8"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2012.02.001"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/S1052623401383248"},{"key":"atypb9","first-page":"606","author":"Ding C.","year":"2005","journal-title":"PA"},{"key":"atypb10","first-page":"126","author":"Ding C.","year":"2006","journal-title":"New York"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614317"},{"key":"atypb12","unstructured":"T. Iguchi, D. G. Mixon, J. Peterson, and S. Villar,\n                      On the Tightness of an SDP Relaxation of $k$-Means\n                      , preprint,https:\/\/arxiv.org\/abs\/1505.04778, 2015."},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2009.09.011"},{"key":"atypb14","unstructured":"L. Kaufman and P. J. Rousseeuw,\n                      Finding Groups in Data: An Introduction to Cluster Analysis\n                      , Wiley Ser. Probab. Stat. 344, John Wiley, New York, 2009."},{"key":"atypb15","first-page":"106","author":"Kuang D.","year":"2012","journal-title":"PA"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/080728214"},{"key":"atypb17","first-page":"362","author":"Li T.","year":"2006","journal-title":"NJ"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"atypb19","first-page":"284","author":"L\u00f6fberg J.","year":"2004","journal-title":"NJ"},{"key":"atypb20","unstructured":"J. MacQueen,\n                      Some methods for classification and analysis of multivariate observations\n                      , in Proceedings of the Fifth Berkeley Symposium on Mathematical Statistics and Probability, Volume 1: Statistics, University of California Press, Oakland, CA, 1967, pp. 281-297."},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iax001"},{"key":"atypb22","unstructured":"P. A. Parrilo,\n                      Structured Semidefinite Programs and Semialgebraic Geometry Methods in Robustness and Optimization\n                      , Ph.D. thesis, California Institute of Technology, Pasadena, CA, 2000."},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1137\/050641983"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.neucom.2014.02.018"},{"key":"atypb25","unstructured":"N. Rujeerapaiboon, K. Schindler, D. Kuhn, and W. Wiesemann,\n                      Size Matters: Cardinality-Constrained Clustering and Outlier Detection via Conic Optimization\n                      , preprint,https:\/\/arxiv.org\/abs\/1705.07837, 2017."},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.28.2.246.14485"}],"container-title":["SIAM Journal on Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/17M1135724","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:52:21Z","timestamp":1787338341000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/17M1135724"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,1]]},"references-count":26,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,1]]}},"alternative-id":["10.1137\/17M1135724"],"URL":"https:\/\/doi.org\/10.1137\/17m1135724","relation":{},"ISSN":["1052-6234","1095-7189"],"issn-type":[{"value":"1052-6234","type":"print"},{"value":"1095-7189","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,1]]}}}