{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,7]],"date-time":"2025-10-07T14:28:58Z","timestamp":1759847338643,"version":"3.37.3"},"reference-count":35,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2019,2,16]],"date-time":"2019-02-16T00:00:00Z","timestamp":1550275200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2019,7]]},"DOI":"10.1007\/s10107-019-01375-2","type":"journal-article","created":{"date-parts":[[2019,2,20]],"date-time":"2019-02-20T16:41:49Z","timestamp":1550680909000},"page":"137-173","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Efficient, certifiably optimal clustering with applications to latent variable graphical models"],"prefix":"10.1007","volume":"176","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-5457-3328","authenticated-orcid":false,"given":"Carson","family":"Eisenach","sequence":"first","affiliation":[]},{"given":"Han","family":"Liu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,2,16]]},"reference":[{"key":"1375_CR1","unstructured":"Bunea, F., Giraud, C., Royer, M., Verzelen, N.: PECOK: a convex optimization approach to variable clustering. \n                    arXiv:1606.05100\n                    \n                   (2016)"},{"key":"1375_CR2","unstructured":"Dasgupta, S.: The hardness of k-means clustering. University of California, San Diego, Tech. rep. (2008)"},{"key":"1375_CR3","doi-asserted-by":"publisher","first-page":"13","DOI":"10.1016\/j.tcs.2010.05.034","volume":"442","author":"M Mahajan","year":"2012","unstructured":"Mahajan, M., Nimbhorkar, P., Varadarajan, K.: The planar k-means problem is NP-hard. Theor. Comput. Sci. 442, 13\u201321 (2012). \n                    https:\/\/doi.org\/10.1016\/j.tcs.2010.05.034","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"1375_CR4","doi-asserted-by":"publisher","first-page":"129","DOI":"10.1109\/TIT.1982.1056489","volume":"28","author":"SP Lloyd","year":"1982","unstructured":"Lloyd, S.P.: Least squares quantization in PCM. IEEE Trans. Inf. Theory 28(2), 129\u2013137 (1982). \n                    https:\/\/doi.org\/10.1109\/TIT.1982.1056489","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"1375_CR5","doi-asserted-by":"publisher","first-page":"364","DOI":"10.1093\/comjnl\/20.4.364","volume":"20","author":"D Defays","year":"1977","unstructured":"Defays, D.: An efficient algorithm for a complete link method. Comput. J. 20(4), 364\u2013366 (1977)","journal-title":"Comput. J."},{"key":"1375_CR6","doi-asserted-by":"crossref","unstructured":"Kumar, A., Kannan, R.: Clustering with spectral norm and the k-means algorithm. In: FOCS. \n                    arXiv:1004.1823v1\n                    \n                   (2010)","DOI":"10.1109\/FOCS.2010.35"},{"key":"1375_CR7","unstructured":"Arthur, D., Vassilvitskii, S.: k-means++: the advantages of careful seeding. In: SODA (2007)"},{"issue":"1","key":"1375_CR8","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). \n                    https:\/\/doi.org\/10.1137\/050641983","journal-title":"SIAM J. Optim."},{"key":"1375_CR9","volume-title":"Approximation Algorithms","author":"V Vazirani","year":"2001","unstructured":"Vazirani, V.: Approximation Algorithms. Springer, Berlin (2001)"},{"key":"1375_CR10","doi-asserted-by":"publisher","unstructured":"Awasthi, P., Bandeira, A.S.: Relax, no need to round: integrality of clustering formulations. In: ITCS, p.\u00a027, \n                    https:\/\/doi.org\/10.1145\/2688073.2688116\n                    \n                  . \n                    arXiv:1408.4045\n                    \n                   (2015)","DOI":"10.1145\/2688073.2688116"},{"key":"1375_CR11","doi-asserted-by":"publisher","unstructured":"Iguchi, T., Mixon, D.G., Peterson, J., Villar, S.: Probably certifiably correct k-means clustering. Mathematical Programming pp 1\u201329. \n                    https:\/\/doi.org\/10.1007\/s10107-016-1097-0\n                    \n                  . \n                    arXiv:1509.07983\n                    \n                   (2016)","DOI":"10.1007\/s10107-016-1097-0"},{"key":"1375_CR12","unstructured":"Bunea, F., Giraud, C., Luo, X., Royer, M., Verzelen, N.: Model assisted variable clustering: minimax-optimal recovery and algorithms. \n                    arXiv:1508.01939\n                    \n                   (2018)"},{"key":"1375_CR13","unstructured":"Bunea, F., Ning, Y., Wegkamp, M.: Overlapping variable clustering with statistical guarantees. \n                    arXiv:1704.06977v1\n                    \n                   (2017)"},{"key":"1375_CR14","unstructured":"Bandeira, A.S.: A note on probably certifiably correct algorithms. \n                    arXiv:1509.00824v1\n                    \n                   (2015)"},{"issue":"1\u20132","key":"1375_CR15","doi-asserted-by":"publisher","first-page":"429","DOI":"10.1007\/s10107-013-0729-x","volume":"147","author":"BPW Ames","year":"2014","unstructured":"Ames, B.P.W.: Guaranteed clustering and biclustering via semidefinite programming. Math. Program. Ser. A 147(1\u20132), 429\u2013465 (2014). \n                    https:\/\/doi.org\/10.1007\/s10107-013-0729-x\n                    \n                  . \n                    arXiv:1202.3663","journal-title":"Math. Program. Ser. A"},{"key":"1375_CR16","unstructured":"Iguchi, T., Mixon, D.G., Peterson, J., Villar, S.: On the tightness of an SDP relaxation of k-means. \n                    arXiv:1505.04778\n                    \n                   (2015)"},{"key":"1375_CR17","unstructured":"Renegar, J.: Efficient first-order methods for linear programming and semidefinite programming. \n                    arXiv:1409.5832\n                    \n                   (2014)"},{"key":"1375_CR18","doi-asserted-by":"publisher","unstructured":"Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press. \n                    https:\/\/doi.org\/10.1080\/10556781003625177\n                    \n                  . \n                    arXiv:1111.6189v1\n                    \n                   (2004)","DOI":"10.1080\/10556781003625177"},{"key":"1375_CR19","doi-asserted-by":"crossref","unstructured":"Arora, S., Hazan, E., Kale, S.: Fast algorithms for approximate semidefinite programming using the multiplicative weights update method. In: FOCS (2005)","DOI":"10.1109\/SFCS.2005.35"},{"issue":"1","key":"1375_CR20","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1561\/2200000016","volume":"3","author":"S Boyd","year":"2011","unstructured":"Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1), 1\u2013122 (2011). \n                    https:\/\/doi.org\/10.1561\/2200000016\n                    \n                  . \n                    arXiv:1408.2927","journal-title":"Found. Trends Mach. Learn."},{"key":"1375_CR21","doi-asserted-by":"crossref","unstructured":"Awasthi, P., Sheffet, O.: Improved spectral-norm bounds for clustering. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 37\u201349. \n                    arXiv:1206.3204v2\n                    \n                   (2012)","DOI":"10.1007\/978-3-642-32512-0_4"},{"key":"1375_CR22","unstructured":"Li, X., Chen, Y., Xu, J.: Convex relaxation methods for community detection. \n                    arXiv:1810.00315\n                    \n                   (2018)"},{"key":"1375_CR23","doi-asserted-by":"crossref","unstructured":"Abbe, E., Bandeira, A.S., Hall, G.: Exact recovery in the stochastic block model. IEEE: Trans. Inf. Theory 62(1) (2016)","DOI":"10.1109\/TIT.2015.2490670"},{"key":"1375_CR24","unstructured":"Pirinen, A., Ames, B.: Clustering of sparse and approximately sparse graphs by semidefinite programming. \n                    arXiv:1603.05296\n                    \n                   (2016)"},{"key":"1375_CR25","doi-asserted-by":"publisher","unstructured":"Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course, vol.\u00a087. Springer US. \n                    https:\/\/doi.org\/10.1007\/978-1-4419-8853-9\n                    \n                  . \n                    arXiv:1011.1669v3\n                    \n                   (2004)","DOI":"10.1007\/978-1-4419-8853-9"},{"key":"1375_CR26","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/s10107-004-0552-5","volume":"103","author":"Y Nesterov","year":"2005","unstructured":"Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. Ser. A 103, 127\u2013152 (2005). \n                    https:\/\/doi.org\/10.1007\/s10107-004-0552-5","journal-title":"Math. Program. Ser. A"},{"issue":"1991","key":"1375_CR27","first-page":"245","volume":"259","author":"Y Nesterov","year":"2007","unstructured":"Nesterov, Y.: Smoothing technique and its applications in semidefinite optimization. Oper. Res. 259(1991), 245\u2013259 (2007)","journal-title":"Oper. Res."},{"issue":"3\u20134","key":"1375_CR28","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1561\/2200000050","volume":"8","author":"S Bubeck","year":"2015","unstructured":"Bubeck, S.: Convex optimization: algorithms and complexity. Found. Trends Mach. Learn. 8(3\u20134), 231\u2013357 (2015). \n                    https:\/\/doi.org\/10.1561\/2200000050\n                    \n                  . \n                    arXiv:1405.4980v2","journal-title":"Found. Trends Mach. Learn."},{"issue":"6","key":"1375_CR29","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1002\/(SICI)1097-0266(199606)17:6<441::AID-SMJ819>3.0.CO;2-G","volume":"17","author":"D Ketchen","year":"1996","unstructured":"Ketchen, D., Shook, C.: The application of cluster analysis in strategic management research: an analysis and critique. Strategic Manag. J. 17(6), 441\u2013458 (1996)","journal-title":"Strategic Manag. J."},{"issue":"3","key":"1375_CR30","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1006\/nimg.1998.0391","volume":"9","author":"C Goutte","year":"1999","unstructured":"Goutte, C., Toft, P., Rostrup, E., Nielsen, F.\u00c5., Hansen, L.K.: On clustering fMRI time series. NeuroImage 9(3), 298\u2013310 (1999). \n                    https:\/\/doi.org\/10.1006\/NIMG.1998.0391","journal-title":"NeuroImage"},{"issue":"3","key":"1375_CR31","doi-asserted-by":"publisher","first-page":"715","DOI":"10.1007\/s10208-013-9150-3","volume":"15","author":"B O\u2019Donoghue","year":"2015","unstructured":"O\u2019Donoghue, B., Cand\u00e8s, E.: Adaptive restart for accelerated gradient schemes. Found. Comput. Math. 15(3), 715\u2013732 (2015). \n                    https:\/\/doi.org\/10.1007\/s10208-013-9150-3\n                    \n                  . \n                    arXiv:1204.3982","journal-title":"Found. Comput. Math."},{"key":"1375_CR32","doi-asserted-by":"publisher","unstructured":"Andersen, E.D., Andersen, K.D.: The Mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm. In: High Performance Optimization, Springer, pp. 197\u2013232. \n                    https:\/\/doi.org\/10.1007\/978-1-4757-3216-0_8\n                    \n                   (2000)","DOI":"10.1007\/978-1-4757-3216-0_8"},{"key":"1375_CR33","unstructured":"Sun, D., Toh, K.C., Yuan, Y., Zhao, X.Y.: SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0). \n                    arXiv:1710.10604\n                    \n                   (2017)"},{"key":"1375_CR34","doi-asserted-by":"crossref","unstructured":"Rudelson, M., Vershynin, R.: Hanson-Wright inequality and sub-Gaussian concentration. \n                    arXiv:1306.2872\n                    \n                   (2013)","DOI":"10.1214\/ECP.v18-2865"},{"key":"1375_CR35","doi-asserted-by":"publisher","unstructured":"Vershynin, R.: Introduction to the non-asymptotic analysis of random matrices. \n                    https:\/\/doi.org\/10.1017\/CBO9780511794308.006\n                    \n                  . \n                    arXiv:1011.3027\n                    \n                   (2011)","DOI":"10.1017\/CBO9780511794308.006"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10107-019-01375-2\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-019-01375-2.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,2,15]],"date-time":"2020-02-15T19:08:45Z","timestamp":1581793725000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10107-019-01375-2"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,2,16]]},"references-count":35,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2019,7]]}},"alternative-id":["1375"],"URL":"https:\/\/doi.org\/10.1007\/s10107-019-01375-2","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2019,2,16]]},"assertion":[{"value":"11 December 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 February 2019","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 February 2019","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}