{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,8]],"date-time":"2026-02-08T07:56:39Z","timestamp":1770537399359,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":28,"publisher":"ACM","license":[{"start":{"date-parts":[[2015,6,14]],"date-time":"2015-06-14T00:00:00Z","timestamp":1434240000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["DGE 1106400, CCF-1320854"],"award-info":[{"award-number":["DGE 1106400, CCF-1320854"]}],"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,6,14]]},"DOI":"10.1145\/2746539.2746604","type":"proceedings-article","created":{"date-parts":[[2015,6,3]],"date-time":"2015-06-03T15:35:56Z","timestamp":1433345756000},"page":"219-228","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":38,"title":["Near Optimal LP Rounding Algorithm for CorrelationClustering on Complete and Complete k-partite Graphs"],"prefix":"10.1145","author":[{"given":"Shuchi","family":"Chawla","sequence":"first","affiliation":[{"name":"University of Wisconsin-Madison, Madison, WI, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Konstantin","family":"Makarychev","sequence":"additional","affiliation":[{"name":"Microsoft Research, Redmond, WA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Tselil","family":"Schramm","sequence":"additional","affiliation":[{"name":"UC Berkeley, Berkeley, CA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Grigory","family":"Yaroslavtsev","sequence":"additional","affiliation":[{"name":"University of Pennsylvania, Philadelphia, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,6,14]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-008-9211-1"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/110848712"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1411509.1411513"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_4"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_1_7_1","first-page":"02","article-title":"Clustering gene expression patterns","volume":"2014","author":"Ben-Dor A.","year":"1999","unstructured":"A. Ben-Dor , R. Shamir , and Z. Yakhini . Clustering gene expression patterns . Journal of Computational Biology, 6(3--4):281--297 , 2014\/11 \/ 02 1999 . A. Ben-Dor, R. Shamir, and Z. Yakhini. Clustering gene expression patterns. Journal of Computational Biology, 6(3--4):281--297, 2014\/11\/02 1999.","journal-title":"Journal of Computational Biology, 6(3--4):281--297"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-006-0210-9"},{"key":"e_1_3_2_1_10_1","first-page":"2204","volume-title":"Advances in Neural Information Processing Systems 25","author":"Chen Y.","year":"2012","unstructured":"Y. Chen , S. Sanghavi , and H. Xu . Clustering sparse graphs. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors , Advances in Neural Information Processing Systems 25 , pages 2204 -- 2212 . Curran Associates, Inc. , 2012 . Y. Chen, S. Sanghavi, and H. Xu. Clustering sparse graphs. In F. Pereira, C. Burges, L. Bottou, and K. Weinberger, editors, Advances in Neural Information Processing Systems 25, pages 2204--2212. Curran Associates, Inc., 2012."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_1_12_1","volume-title":"In ACM SIGIR-2001 Workshop on Mathematical\/Formal Methods in Information Retrieval","author":"Cohen W.","year":"2001","unstructured":"W. Cohen and J. Richman . Learning to match and cluster entity names . In In ACM SIGIR-2001 Workshop on Mathematical\/Formal Methods in Information Retrieval , 2001 . W. Cohen and J. Richman. Learning to match and cluster entity names. In In ACM SIGIR-2001 Workshop on Mathematical\/Formal Methods in Information Retrieval, 2001."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/775047.775116"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.05.008"},{"key":"e_1_3_2_1_15_1","first-page":"61","volume-title":"Thirty-Third Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia, January 18--22, 2010","author":"Downing N.","year":"2010","unstructured":"N. Downing , P. J. Stuckey , and A. Wirth . Improved consensus clustering via linear programming. In Computer Science 2010 , Thirty-Third Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia, January 18--22, 2010 , Proceedings , pages 61 -- 70 , 2010 . N. Downing, P. J. Stuckey, and A. Wirth. Improved consensus clustering via linear programming. In Computer Science 2010, Thirty-Third Australasian Computer Science Conference (ACSC 2010), Brisbane, Australia, January 18--22, 2010, Proceedings, pages 61--70, 2010."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/951951.952295"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217303"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109686"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536458"},{"key":"e_1_3_2_1_20_1","volume-title":"Algorithms for semi-random correlation clustering. arXiv preprint arXiv:1406.5667","author":"Makarychev K.","year":"2014","unstructured":"K. Makarychev , Y. Makarychev , and A. Vijayaraghavan . Algorithms for semi-random correlation clustering. arXiv preprint arXiv:1406.5667 , 2014 . K. Makarychev, Y. Makarychev, and A. Vijayaraghavan. Algorithms for semi-random correlation clustering. arXiv preprint arXiv:1406.5667, 2014."},{"key":"e_1_3_2_1_21_1","first-page":"573","volume-title":"27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Mathieu C.","year":"2010","unstructured":"C. Mathieu , O. Sankur , and W. Schudy . Online Correlation Clustering. In J.-Y. Marion and T. Schwentick, editors , 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs) , pages 573 -- 584 , Dagstuhl, Germany , 2010 . Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik. C. Mathieu, O. Sankur, and W. Schudy. Online Correlation Clustering. In J.-Y. Marion and T. Schwentick, editors, 27th International Symposium on Theoretical Aspects of Computer Science, volume 5 of Leibniz International Proceedings in Informatics (LIPIcs), pages 573--584, Dagstuhl, Germany, 2010. Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873659"},{"key":"e_1_3_2_1_23_1","first-page":"905","volume-title":"NIPS","author":"Mccallum A.","year":"2003","unstructured":"A. Mccallum and B. Wellner . Toward conditional models of identity uncertainty with application to proper noun coreference . In In NIPS , pages 905 -- 912 . MIT Press , 2003 . A. Mccallum and B. Wellner. Toward conditional models of identity uncertainty with application to proper noun coreference. In In NIPS, pages 905--912. MIT Press, 2003."},{"key":"e_1_3_2_1_24_1","first-page":"526","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04","author":"Swamy C.","year":"2004","unstructured":"C. Swamy . Correlation clustering : Maximizing agreements via semidefinite programming . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04 , pages 526 -- 527 , Philadelphia, PA, USA , 2004 . Society for Industrial and Applied Mathematics. C. Swamy. Correlation clustering: Maximizing agreements via semidefinite programming. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '04, pages 526--527, Philadelphia, PA, USA, 2004. Society for Industrial and Applied Mathematics."},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.06.004"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/1625275.1625558"},{"key":"e_1_3_2_1_27_1","first-page":"405","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"van Zuylen A.","year":"2007","unstructured":"A. van Zuylen , R. Hegde , K. Jain , and D. P. Williamson . Deterministic pivoting algorithms for constrained ranking and clustering problems . In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 , New Orleans, Louisiana, USA, January 7--9 , 2007 , pages 405 -- 414 , 2007. A. van Zuylen, R. Hegde, K. Jain, and D. P. Williamson. Deterministic pivoting algorithms for constrained ranking and clustering problems. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7--9, 2007, pages 405--414, 2007."},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1971947"},{"key":"e_1_3_2_1_29_1","first-page":"227","volume-title":"Encyclopedia of Machine Learning","author":"Wirth A.","year":"2010","unstructured":"A. Wirth . Correlation clustering. In C. Sammut and G. Webb, editors, Encyclopedia of Machine Learning , pages 227 -- 231 . Springer US , 2010 . A. Wirth. Correlation clustering. In C. Sammut and G. Webb, editors, Encyclopedia of Machine Learning, pages 227--231. Springer US, 2010."}],"event":{"name":"STOC '15: Symposium on Theory of Computing","location":"Portland Oregon USA","acronym":"STOC '15","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the forty-seventh annual ACM symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746604","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2746539.2746604","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:17:00Z","timestamp":1750227420000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2746539.2746604"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,6,14]]},"references-count":28,"alternative-id":["10.1145\/2746539.2746604","10.1145\/2746539"],"URL":"https:\/\/doi.org\/10.1145\/2746539.2746604","relation":{},"subject":[],"published":{"date-parts":[[2015,6,14]]},"assertion":[{"value":"2015-06-14","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}