{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:19:42Z","timestamp":1774941582573,"version":"3.50.1"},"reference-count":29,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T00:00:00Z","timestamp":1538179200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T00:00:00Z","timestamp":1538179200000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["1620455"],"award-info":[{"award-number":["1620455"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["1737943"],"award-info":[{"award-number":["1737943"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2020,1]]},"DOI":"10.1007\/s10107-018-1333-x","type":"journal-article","created":{"date-parts":[[2018,9,29]],"date-time":"2018-09-29T02:11:18Z","timestamp":1538187078000},"page":"295-341","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":21,"title":["When do birds of a feather flock together? k-Means, proximity, and conic programming"],"prefix":"10.1007","volume":"179","author":[{"given":"Xiaodong","family":"Li","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2866-715X","authenticated-orcid":false,"given":"Yang","family":"Li","sequence":"additional","affiliation":[]},{"given":"Shuyang","family":"Ling","sequence":"additional","affiliation":[]},{"given":"Thomas","family":"Strohmer","sequence":"additional","affiliation":[]},{"given":"Ke","family":"Wei","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2018,9,29]]},"reference":[{"key":"1333_CR1","doi-asserted-by":"publisher","first-page":"458","DOI":"10.1007\/11503415_31","volume-title":"Learning Theory","author":"Dimitris Achlioptas","year":"2005","unstructured":"Achlioptas, D., McSherry, F.: On spectral learning of mixtures of distributions. In: International Conference on Computational Learning Theory, pp. 458\u2013469. Springer, New York (2005)"},{"issue":"2","key":"1333_CR2","doi-asserted-by":"publisher","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(2), 245\u2013248 (2009)","journal-title":"Mach. Learn."},{"issue":"1","key":"1333_CR3","doi-asserted-by":"publisher","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. Stat. 46(1), 149\u2013179 (2018)","journal-title":"Ann. Stat."},{"issue":"5","key":"1333_CR4","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1145\/2027216.2027217","volume":"58","author":"D Arthur","year":"2011","unstructured":"Arthur, D., Manthey, B., R\u00f6glin, H.: Smoothed analysis of the k-means method. J. ACM (JACM) 58(5), 19 (2011)","journal-title":"J. ACM (JACM)"},{"key":"1333_CR5","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. ACM (2015)","DOI":"10.1145\/2688073.2688116"},{"key":"1333_CR6","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/978-3-642-32512-0_4","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Pranjal Awasthi","year":"2012","unstructured":"Awasthi, P., Sheffet, O.: Improved spectral-norm bounds for clustering. In: APPROX-RANDOM, pp. 37\u201349. Springer, New York (2012)"},{"key":"1333_CR7","doi-asserted-by":"crossref","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on modern convex optimization: analysis, algorithms, and engineering applications. SIAM (2001)","DOI":"10.1137\/1.9780898718829"},{"key":"1333_CR8","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804441","volume-title":"Convex Optimization","author":"S Boyd","year":"2004","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)"},{"key":"1333_CR9","doi-asserted-by":"crossref","unstructured":"Dasgupta, S.: Learning mixtures of gaussians. In: 40th Annual Symposium on Foundations of Computer Science, pp. 634\u2013644. IEEE (1999)","DOI":"10.1109\/SFFCS.1999.814639"},{"issue":"4","key":"1333_CR10","doi-asserted-by":"publisher","first-page":"637","DOI":"10.1137\/S0036144599352836","volume":"41","author":"Q Du","year":"1999","unstructured":"Du, Q., Faber, V., Gunzburger, M.: Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. 41(4), 637\u2013676 (1999)","journal-title":"SIAM Rev."},{"key":"1333_CR11","volume-title":"Matrix Computations","author":"GH Golub","year":"1996","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, 3rd edn. The Johns Hopkins University Press, Baltimore (1996)","edition":"3"},{"key":"1333_CR12","unstructured":"Iguchi, T., Mixon, D.G., Peterson, J., Villar, S.: On the tightness of an SDP relaxation of k-means (2015). arXiv preprint arXiv:1505.04778"},{"issue":"2","key":"1333_CR13","doi-asserted-by":"publisher","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. Progr. 165(2), 605\u2013642 (2017)","journal-title":"Math. Progr."},{"issue":"3\u20134","key":"1333_CR14","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1561\/0400000025","volume":"4","author":"R Kannan","year":"2009","unstructured":"Kannan, R., Vempala, S.: Spectral algorithms. Found. Trends Theor. Comput. Sci. 4(3\u20134), 157\u2013288 (2009)","journal-title":"Found. Trends Theor. Comput. Sci."},{"key":"1333_CR15","doi-asserted-by":"crossref","unstructured":"Kumar, A., Kannan, R.: Clustering with spectral norm and the k-means algorithm. In: 2010 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 299\u2013308. IEEE (2010)","DOI":"10.1109\/FOCS.2010.35"},{"key":"1333_CR16","unstructured":"Ling, S., Strohmer, T.: Certifying global optimality of graph cuts via semidefinite relaxation: a performance guarantee for spectral clustering (2018). arXiv preprint arXiv:1806.11429"},{"issue":"2","key":"1333_CR17","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"},{"key":"1333_CR18","unstructured":"Lu, Y., Zhou, H.H.: Statistical and computational guarantees of Lloyd\u2019s algorithm and its variants (2016). arXiv preprint arXiv:1612.02099"},{"key":"1333_CR19","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-642-00202-1_24","volume-title":"WALCOM: Algorithms and Computation","author":"Meena Mahajan","year":"2009","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. In: International Workshop on Algorithms and Computation, pp. 274\u2013285. Springer, New York (2009)"},{"issue":"4","key":"1333_CR20","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1093\/imaiai\/iax001","volume":"6","author":"DG Mixon","year":"2017","unstructured":"Mixon, D.G., Villar, S., Ward, R.: Clustering subgaussian mixtures by semidefinite programming. Inf. Inference: J. IMA 6(4), 389\u2013415 (2017)","journal-title":"Inf. Inference: J. IMA"},{"issue":"1","key":"1333_CR21","doi-asserted-by":"publisher","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. Opt. 18(1), 186\u2013205 (2007)","journal-title":"SIAM J. Opt."},{"issue":"1","key":"1333_CR22","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1109\/TPAMI.1984.4767478","volume":"6","author":"SZ Selim","year":"1984","unstructured":"Selim, S.Z., Ismail, M.A.: k-Means-type algorithms: a generalized convergence theorem and characterization of local optimality. IEEE Trans. Pattern Anal. Mach. Intell. 6(1), 81\u201387 (1984)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"4","key":"1333_CR23","doi-asserted-by":"publisher","first-page":"389","DOI":"10.1007\/s10208-011-9099-z","volume":"12","author":"JA Tropp","year":"2012","unstructured":"Tropp, J.A.: User-friendly tail bounds for sums of random matrices. Found. Comput. Math. 12(4), 389\u2013434 (2012)","journal-title":"Found. Comput. Math."},{"issue":"4","key":"1333_CR24","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/s00454-011-9340-1","volume":"45","author":"A Vattani","year":"2011","unstructured":"Vattani, A.: k-Means requires exponentially many iterations even in the plane. Discrete Comput. Geom. 45(4), 596\u2013616 (2011)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"1333_CR25","doi-asserted-by":"publisher","first-page":"841","DOI":"10.1016\/j.jcss.2003.11.008","volume":"68","author":"S Vempala","year":"2004","unstructured":"Vempala, S., Wang, G.: A spectral algorithm for learning mixture models. J. Comput. Syst. Sci. 68(4), 841\u2013860 (2004)","journal-title":"J. Comput. Syst. Sci."},{"key":"1333_CR26","volume-title":"Compressed Sensing: Theory and Applications, Chapter 5","author":"R Vershynin","year":"2012","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. In: Eldar, Y.C., Kutyniok, G. (eds.) Compressed Sensing: Theory and Applications, Chapter 5. Cambridge University Press, Cambridge (2012)"},{"key":"1333_CR27","doi-asserted-by":"crossref","unstructured":"Wright, S.J.: Primal-dual interior-point methods. SIAM (1997)","DOI":"10.1137\/1.9781611971453"},{"issue":"3","key":"1333_CR28","doi-asserted-by":"publisher","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. Progr. 7(3), 331\u2013366 (2015)","journal-title":"Math. Progr."},{"issue":"4","key":"1333_CR29","doi-asserted-by":"publisher","first-page":"1737","DOI":"10.1137\/080718206","volume":"20","author":"X-Y Zhao","year":"2010","unstructured":"Zhao, X.-Y., Sun, D., Toh, K.-C.: A Newton-CG augmented Lagrangian method for semidefinite programming. SIAM J. Opt. 20(4), 1737\u20131765 (2010)","journal-title":"SIAM J. Opt."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1333-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-018-1333-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-018-1333-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T14:22:48Z","timestamp":1760451768000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-018-1333-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,9,29]]},"references-count":29,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2020,1]]}},"alternative-id":["1333"],"URL":"https:\/\/doi.org\/10.1007\/s10107-018-1333-x","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,9,29]]},"assertion":[{"value":"16 October 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 September 2018","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"29 September 2018","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}