{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T07:19:40Z","timestamp":1774941580482,"version":"3.50.1"},"reference-count":26,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,12,21]],"date-time":"2016-12-21T00:00:00Z","timestamp":1482278400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,12,21]],"date-time":"2016-12-21T00:00:00Z","timestamp":1482278400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["Young Investigator Research Program"],"award-info":[{"award-number":["Young Investigator Research Program"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["F4FGA05076J002"],"award-info":[{"award-number":["F4FGA05076J002"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000086","name":"Directorate for Mathematical and Physical Sciences","doi-asserted-by":"publisher","award":["1321779"],"award-info":[{"award-number":["1321779"]}],"id":[{"id":"10.13039\/100000086","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CAREER"],"award-info":[{"award-number":["CAREER"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s10107-016-1097-0","type":"journal-article","created":{"date-parts":[[2016,12,21]],"date-time":"2016-12-21T18:03:23Z","timestamp":1482343403000},"page":"605-642","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":20,"title":["Probably certifiably correct k-means clustering"],"prefix":"10.1007","volume":"165","author":[{"given":"Takayuki","family":"Iguchi","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2743-7010","authenticated-orcid":false,"given":"Dustin G.","family":"Mixon","sequence":"additional","affiliation":[]},{"given":"Jesse","family":"Peterson","sequence":"additional","affiliation":[]},{"given":"Soledad","family":"Villar","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,12,21]]},"reference":[{"issue":"1","key":"1097_CR1","doi-asserted-by":"publisher","first-page":"471","DOI":"10.1109\/TIT.2015.2490670","volume":"62","author":"E Abbe","year":"2016","unstructured":"Abbe, E., Bandeira, A.S., Hall, G.: Exact recovery in the stochastic block model. IEEE Trans. Inf. Theory 62(1), 471\u2013487 (2016)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"1097_CR2","doi-asserted-by":"crossref","unstructured":"Abbe, E., Sandon, C.: Community detection in general stochastic block models: fundamental limits and efficient algorithms for recovery. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, pp. 670\u2013688, 17\u201320 October 2015","DOI":"10.1109\/FOCS.2015.47"},{"key":"1097_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 (2007)"},{"key":"1097_CR4","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"},{"issue":"3","key":"1097_CR5","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1016\/j.crma.2015.11.009","volume":"354","author":"AS Bandeira","year":"2015","unstructured":"Bandeira, A.S.: A note on probably certifiably correct algorithms. C. R. Math. 354(3), 329\u2013333 (2015)","journal-title":"C. R. Math."},{"key":"1097_CR6","doi-asserted-by":"crossref","unstructured":"Chen, H., Peng, J.: 0\u20131 Semidefinite programming for graph-cut clustering: modelling and approximation. In: Data Mining and Mathematical Programming. CRM Proceedings and Lecture Notes of the American Mathematical Society, pp. 15\u201340 (2008)","DOI":"10.1090\/crmp\/045\/02"},{"key":"1097_CR7","doi-asserted-by":"crossref","unstructured":"Dhillon, I.S., Guan, Y., Kulis, B.: Kernel k-means: spectral clustering and normalized cuts. In: Proceedings of the Tenth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 551\u2013556. ACM (2004)","DOI":"10.1145\/1014052.1014118"},{"issue":"11","key":"1097_CR8","doi-asserted-by":"publisher","first-page":"1944","DOI":"10.1109\/TPAMI.2007.1115","volume":"29","author":"IS Dhillon","year":"2007","unstructured":"Dhillon, I.S., Guan, Y., Kulis, B.: Weighted graph cuts without eigenvectors a multilevel approach. IEEE Trans. Pattern Anal. Mach. Intell. 29(11), 1944\u20131957 (2007)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"1097_CR9","unstructured":"Elhamifar, E., Sapiro, G., Vidal, R.: Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. In: Advances in Neural Information Processing Systems, pp. 19\u201327 (2012)"},{"key":"1097_CR10","volume-title":"Matrix Computations","author":"GH Golub","year":"2012","unstructured":"Golub, G.H., Van Loan, C.F.: Matrix Computations, vol. 3. JHU Press, Baltimore (2012)"},{"key":"1097_CR11","doi-asserted-by":"crossref","unstructured":"Grant, M., Boyd, S., Ye, Y.: Graph implementations for nonsmooth convex programs. In: Blondel, V., Boyd, S., Kimura,H., (eds.) Recent Advances in Learning and Control. Lecture Notes in Control and Information Sciences. Springer, London, pp. 95\u2013110 (2008)","DOI":"10.1007\/978-1-84800-155-8_7"},{"key":"1097_CR12","unstructured":"Grant, M., Boyd, S.: CVX: matlab software for disciplined convex programming, version 2.1 (2014). http:\/\/cvxr.com\/cvx"},{"key":"1097_CR13","unstructured":"Iguchi, T., Mixon, D.G., Peterson, J., Villar, S.: On the tightness of an SDP relaxation of k-means. arXiv preprint arXiv:1505.04778 (2015)"},{"key":"1097_CR14","doi-asserted-by":"crossref","unstructured":"Jain, K., Mahdian, M., Saberi, A.: A new greedy approach for facility location problems. In: Proceedings of the 34th Annual ACM Symposium on Theory of Computing (2002)","DOI":"10.1145\/509907.510012"},{"key":"1097_CR15","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1214\/aos\/1015957395","volume":"28","author":"B Laurent","year":"2000","unstructured":"Laurent, B., Massart, P.: Adaptive estimation of a quadratic functional by model selection. Ann. Stat. 28, 1302\u20131338 (2000)","journal-title":"Ann. Stat."},{"issue":"2","key":"1097_CR16","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":"12","key":"1097_CR17","doi-asserted-by":"publisher","first-page":"3397","DOI":"10.1109\/78.258082","volume":"41","author":"SG Mallat","year":"1993","unstructured":"Mallat, S.G., Zhang, Z.: Matching pursuits with time-frequency dictionaries. IEEE Trans. Sig. Process. 41(12), 3397\u20133415 (1993)","journal-title":"IEEE Trans. Sig. Process."},{"key":"1097_CR18","unstructured":"Mixon, D.G.: Cone programming cheat sheet. Short, Fat Matrices (weblog) (2015)"},{"key":"1097_CR19","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/j.ic.2015.09.002","volume":"245","author":"A Nellore","year":"2015","unstructured":"Nellore, A., Ward, R.: Recovery guarantees for exemplar-based clustering. Inf. Comput. 245, 165\u2013180 (2015)","journal-title":"Inf. Comput."},{"key":"1097_CR20","doi-asserted-by":"publisher","unstructured":"Nesterov, Y., Nemirovskii, A.: Interior-Point Polynomial Algorithms in Convex Programming, vol. 13. SIAM, Philadelphia (1994). doi: 10.1137\/1.9781611970791","DOI":"10.1137\/1.9781611970791"},{"key":"1097_CR21","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Rabani, Y., Schulman, L., Swamy, C.: The effectiveness of lloyd-type methods for the k-means problem. In: Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (2006)","DOI":"10.1109\/FOCS.2006.75"},{"issue":"1","key":"1097_CR22","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. Optim. 18(1), 186\u2013205 (2007)","journal-title":"SIAM J. Optim."},{"issue":"4","key":"1097_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."},{"key":"1097_CR24","doi-asserted-by":"crossref","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. arXiv:1011.3027v7 (2011)","DOI":"10.1017\/CBO9780511794308.006"},{"key":"1097_CR25","doi-asserted-by":"crossref","unstructured":"Vinayak, R.K., Hassibi, B.: Similarity clustering in the presence of outliers: Exact recovery via convex program. In: IEEE International Symposium on Information Theory, ISIT 2016, Barcelona, Spain, pp. 91\u201395, 10\u201315 July 2016","DOI":"10.1109\/ISIT.2016.7541267"},{"issue":"2","key":"1097_CR26","doi-asserted-by":"crossref","first-page":"29","DOI":"10.32614\/RJ-2011-015","volume":"3","author":"H Wang","year":"2011","unstructured":"Wang, H., Song, M.: Ckmeans.1d.dp: optimal k-means clustering in one dimension by dynamic programming. R J. 3(2), 29\u201333 (2011)","journal-title":"R J."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-016-1097-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1097-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-016-1097-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,19]],"date-time":"2022-07-19T18:34:32Z","timestamp":1658255672000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-016-1097-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,21]]},"references-count":26,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["1097"],"URL":"https:\/\/doi.org\/10.1007\/s10107-016-1097-0","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,21]]},"assertion":[{"value":"23 April 2016","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 November 2016","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 December 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}