{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,20]],"date-time":"2026-05-20T05:38:45Z","timestamp":1779255525094,"version":"3.51.4"},"publisher-location":"New York, NY, USA","reference-count":56,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,1,11]],"date-time":"2015-01-11T00:00:00Z","timestamp":1420934400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-12-1-0317"],"award-info":[{"award-number":["FA9550-12-1-0317"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1218687, CCF-1302518, CAREER"],"award-info":[{"award-number":["CCF-1218687, CCF-1302518, CAREER"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2015,1,11]]},"DOI":"10.1145\/2688073.2688116","type":"proceedings-article","created":{"date-parts":[[2015,1,12]],"date-time":"2015-01-12T20:42:45Z","timestamp":1421095365000},"page":"191-200","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":37,"title":["Relax, No Need to Round"],"prefix":"10.1145","author":[{"given":"Pranjal","family":"Awasthi","sequence":"first","affiliation":[{"name":"Princeton University, Princeton, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Afonso S.","family":"Bandeira","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Moses","family":"Charikar","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravishankar","family":"Krishnaswamy","sequence":"additional","affiliation":[{"name":"Princeton University, Princeton, NJ, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Soledad","family":"Villar","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rachel","family":"Ward","sequence":"additional","affiliation":[{"name":"University of Texas at Austin, Austin, TX, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,1,11]]},"reference":[{"key":"e_1_3_2_1_1_1","volume-title":"Exact recovery in the stochastic block model. arXiv preprint arXiv:1405.3267","author":"Abbe E.","year":"2014","unstructured":"E. Abbe , A. S. Bandeira , and G. Hall . Exact recovery in the stochastic block model. arXiv preprint arXiv:1405.3267 , 2014 . E. Abbe, A. S. Bandeira, and G. Hall. Exact recovery in the stochastic block model. arXiv preprint arXiv:1405.3267, 2014."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/11503415_31"},{"key":"e_1_3_2_1_3_1","volume-title":"k-means++ under approximation stability. The 10th annual conference on Theory and Applications of Models of Computation","author":"Agarwal M.","year":"2013","unstructured":"M. Agarwal , R. Jaiswal , and A. Pal . k-means++ under approximation stability. The 10th annual conference on Theory and Applications of Models of Computation , 2013 . M. Agarwal, R. Jaiswal, and A. Pal. k-means++ under approximation stability. The 10th annual conference on Theory and Applications of Models of Computation, 2013."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10994-009-5103-0"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-013-0729-x"},{"key":"e_1_3_2_1_6_1","volume-title":"Robust convex relaxation for the planted clique and densest k-subgraph problems. arXiv preprint arXiv:1305.4891","author":"Ames B.","year":"2013","unstructured":"B. Ames . Robust convex relaxation for the planted clique and densest k-subgraph problems. arXiv preprint arXiv:1305.4891 , 2013 . B. Ames. Robust convex relaxation for the planted clique and densest k-subgraph problems. arXiv preprint arXiv:1305.4891, 2013."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536418"},{"key":"e_1_3_2_1_8_1","volume-title":"STOC","author":"Arora S.","year":"2005","unstructured":"S. Arora and R. Kannan . Learning mixtures of arbitrary gaussians . STOC , 2005 . S. Arora and R. Kannan. Learning mixtures of arbitrary gaussians. STOC, 2005."},{"key":"e_1_3_2_1_9_1","unstructured":"D. Arthur and S. Vassilvitskii. k-means D. Arthur and S. Vassilvitskii. k-means"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms","year":"2007","unstructured":": the advantages of careful seeding . Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms , 2007 . : the advantages of careful seeding. Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, 2007."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702416402"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688116"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496886"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374474"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_6"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2554797.2554839"},{"key":"e_1_3_2_1_17_1","volume-title":"Conference on Learning Theory (COLT 2014","author":"Bandeira A. S.","year":"2014","unstructured":"A. S. Bandeira , Y. Khoo , and A. Singer . Open problem: Tightness of maximum likelihood semidefinite relaxations . Conference on Learning Theory (COLT 2014 ), Open problem session , 2014 . A. S. Bandeira, Y. Khoo, and A. Singer. Open problem: Tightness of maximum likelihood semidefinite relaxations. Conference on Learning Theory (COLT 2014), Open problem session, 2014."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the First Symposium on Innovations in Computer Science","author":"Bilu Y.","year":"2010","unstructured":"Y. Bilu and N. Linial . Are stable instances easy ? Proceedings of the First Symposium on Innovations in Computer Science , 2010 . Y. Bilu and N. Linial. Are stable instances easy? Proceedings of the First Symposium on Innovations in Computer Science, 2010."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.48"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.862083"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2044061"},{"key":"e_1_3_2_1_22_1","volume-title":"Learning mixtures of gaussians using the k-means algorithm. arXiv preprint arXiv:0912.0086","author":"Chaudhuri K.","year":"2009","unstructured":"K. Chaudhuri , S. Dasgupta , and A. Vattani . Learning mixtures of gaussians using the k-means algorithm. arXiv preprint arXiv:0912.0086 , 2009 . K. Chaudhuri, S. Dasgupta, and A. Vattani. Learning mixtures of gaussians using the k-means algorithm. arXiv preprint arXiv:0912.0086, 2009."},{"key":"e_1_3_2_1_23_1","first-page":"674","volume-title":"Proceedings of The 31st International Conference on Machine Learning","author":"Chen Y.","year":"2014","unstructured":"Y. Chen , S. Bhojanapalli , S. Sanghavi , and R. Ward . Coherent matrix completion . Proceedings of The 31st International Conference on Machine Learning , pages 674 -- 682 , 2014 . Y. Chen, S. Bhojanapalli, S. Sanghavi, and R. Ward. Coherent matrix completion. Proceedings of The 31st International Conference on Machine Learning, pages 674--682, 2014."},{"key":"e_1_3_2_1_24_1","first-page":"2204","volume-title":"NIPS","author":"Chen Y.","year":"2012","unstructured":"Y. Chen , S. Sanghavi , and H. Xu . Clustering sparse graphs . NIPS , pages 2204 -- 2212 , 2012 . Y. Chen, S. Sanghavi, and H. Xu. Clustering sparse graphs. NIPS, pages 2204--2212, 2012."},{"key":"e_1_3_2_1_25_1","volume-title":"Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267","author":"Chen Y.","year":"2014","unstructured":"Y. Chen and J. Xu . Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267 , 2014 . Y. Chen and J. Xu. Statistical-computational tradeoffs in planted problems and submatrix localization with a growing number of clusters and submatrices. arXiv preprint arXiv:1402.1267, 2014."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796496"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2008.926452"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevE.84.066106"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871582"},{"key":"e_1_3_2_1_30_1","first-page":"19","volume-title":"Advances in Neural Information Processing Systems","author":"Elhamifar E.","year":"2012","unstructured":"E. Elhamifar , G. Sapiro , and R. Vidal . Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery . Advances in Neural Information Processing Systems , pages 19 -- 27 , 2012 . E. Elhamifar, G. Sapiro, and R. Vidal. Finding exemplars from pairwise dissimilarities via simultaneous sparse recovery. Advances in Neural Information Processing Systems, pages 19--27, 2012."},{"key":"e_1_3_2_1_31_1","volume-title":"Convex relaxation for finding planted influential nodes in a social network. arXiv preprint arXiv:1307.4047","author":"Elkin L.","year":"2013","unstructured":"L. Elkin , T. Pong , and S. Vavasis . Convex relaxation for finding planted influential nodes in a social network. arXiv preprint arXiv:1307.4047 , 2013 . L. Elkin, T. Pong, and S. Vavasis. Convex relaxation for finding planted influential nodes in a social network. arXiv preprint arXiv:1307.4047, 2013."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.887523"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2004.842696"},{"key":"e_1_3_2_1_34_1","unstructured":"M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming version 2.1. http:\/\/cvxr.com\/cvx Mar. 2014. M. Grant and S. Boyd. CVX: Matlab software for disciplined convex programming version 2.1. http:\/\/cvxr.com\/cvx Mar. 2014."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2104999"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510012"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/375827.375845"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/513400.513402"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-88690-7_60"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.35"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488723"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1982.1056489"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634141"},{"key":"e_1_3_2_1_45_1","volume-title":"SODA","author":"Man-Cho So A.","year":"2010","unstructured":"A. Man-Cho So . Probabilistic analysis of the semidefinite relaxation detector in digital communications . SODA , 2010 . A. Man-Cho So. Probabilistic analysis of the semidefinite relaxation detector in digital communications. SODA, 2010."},{"key":"e_1_3_2_1_46_1","volume-title":"Consistency thresholds for binary symmetric block models. arXiv preprint arXiv:1407.1591","author":"Mossel E.","year":"2014","unstructured":"E. Mossel , J. Neeman , and A. Sly . Consistency thresholds for binary symmetric block models. arXiv preprint arXiv:1407.1591 , 2014 . E. Mossel, J. Neeman, and A. Sly. Consistency thresholds for binary symmetric block models. arXiv preprint arXiv:1407.1591, 2014."},{"key":"e_1_3_2_1_47_1","volume-title":"Recovery guarantees for exemplar-based clustering. arXiv:1309.3256","author":"Nellore A.","year":"2013","unstructured":"A. Nellore and R. Ward . Recovery guarantees for exemplar-based clustering. arXiv:1309.3256 , 2013 . A. Nellore and R. Ward. Recovery guarantees for exemplar-based clustering. arXiv:1309.3256, 2013."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.75"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/050641983"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1007\/11362197_4","volume-title":"A new theoretical framework for k-means-type clustering. Foundations and advances in data mining","author":"Peng J.","year":"2005","unstructured":"J. Peng and Y. Xia . A new theoretical framework for k-means-type clustering. Foundations and advances in data mining , pages 79 -- 96 . Springer , 2005 . J. Peng and Y. Xia. A new theoretical framework for k-means-type clustering. Foundations and advances in data mining, pages 79--96. Springer, 2005."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/1953048.2185803"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/070697835"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/1870658.1870659"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.5555\/17634"},{"key":"e_1_3_2_1_55_1","volume-title":"UAI","author":"Sontag D.","year":"2008","unstructured":"D. Sontag , T. Meltzer , A. Globerson , T. Jaakkola , and Y. Weiss . Tightening LP relaxations for MAP using message passing . UAI , 2008 . D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss. Tightening LP relaxations for MAP using message passing. UAI, 2008."},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/500776"}],"event":{"name":"ITCS'15: Innovations in Theoretical Computer Science","location":"Rehovot Israel","acronym":"ITCS'15","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688116","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2688073.2688116","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:04Z","timestamp":1750227184000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2688073.2688116"}},"subtitle":["Integrality of Clustering Formulations"],"short-title":[],"issued":{"date-parts":[[2015,1,11]]},"references-count":56,"alternative-id":["10.1145\/2688073.2688116","10.1145\/2688073"],"URL":"https:\/\/doi.org\/10.1145\/2688073.2688116","relation":{},"subject":[],"published":{"date-parts":[[2015,1,11]]},"assertion":[{"value":"2015-01-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}