{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,5]],"date-time":"2025-05-05T09:42:13Z","timestamp":1746438133513},"publisher-location":"Cham","reference-count":26,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319592497"},{"type":"electronic","value":"9783319592503"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-59250-3_12","type":"book-chapter","created":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:04:39Z","timestamp":1495544679000},"page":"136-147","source":"Crossref","is-referenced-by-count":11,"title":["Local Guarantees in Graph Cuts and Clustering"],"prefix":"10.1007","author":[{"given":"Moses","family":"Charikar","sequence":"first","affiliation":[]},{"given":"Neha","family":"Gupta","sequence":"additional","affiliation":[]},{"given":"Roy","family":"Schwartz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,5,24]]},"reference":[{"issue":"5","key":"12_CR1","doi-asserted-by":"crossref","first-page":"1110","DOI":"10.1137\/110848712","volume":"41","author":"N Ailon","year":"2012","unstructured":"Ailon, N., Avigdor-Elgrabli, N., Liberty, E., van Zuylen, A.: Improved approximation algorithms for bipartite correlation clustering. SIAM J. Comput. 41(5), 1110\u20131121 (2012)","journal-title":"SIAM J. Comput."},{"issue":"5","key":"12_CR2","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1145\/1411509.1411513","volume":"55","author":"N Ailon","year":"2008","unstructured":"Ailon, N., Charikar, M., Newman, A.: Aggregating inconsistent information: ranking and clustering. J. ACM (JACM) 55(5), 23 (2008)","journal-title":"J. ACM (JACM)"},{"key":"12_CR3","unstructured":"Amit, N.: The bicluster graph editing problem. Ph.D. thesis, Tel Aviv University (2004)"},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"Balcan, M.F., Blum, A., Mansour, Y.: Improved equilibria via public service advertising. In: SODA 2009, pp. 728\u2013737 (2009)","DOI":"10.1137\/1.9781611973068.80"},{"issue":"1\u20133","key":"12_CR5","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/B:MACH.0000033116.57574.95","volume":"56","author":"N Bansal","year":"2004","unstructured":"Bansal, N., Blum, A., Chawla, S.: Correlation clustering. Mach. Learn. 56(1\u20133), 89\u2013113 (2004)","journal-title":"Mach. Learn."},{"issue":"2","key":"12_CR6","doi-asserted-by":"crossref","first-page":"872","DOI":"10.1137\/120873996","volume":"43","author":"N Bansal","year":"2014","unstructured":"Bansal, N., Feige, U., Krauthgamer, R., Makarychev, K., Nagarajan, V., Naor, J., Schwartz, R.: Min-max graph partitioning and small set expansion. SIAM J. Comput. 43(2), 872\u2013904 (2014)","journal-title":"SIAM J. Comput."},{"issue":"3\u20134","key":"12_CR7","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1089\/106652799318274","volume":"6","author":"A Ben-Dor","year":"1999","unstructured":"Ben-Dor, A., Shamir, R., Yakhini, Z.: Clustering gene expression patterns. J. Comput. Biol. 6(3\u20134), 281\u2013297 (1999)","journal-title":"J. Comput. Biol."},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Chakraborty, T., Khanna, S.: Approximating pure nash equilibrium in cut, party affiliation, and satisfiability games. In: EC 2010, pp. 73\u201382 (2010)","DOI":"10.1145\/1807342.1807353"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. In: FOCS 2003, pp. 524\u2013533 (2003)","DOI":"10.1109\/SFCS.2003.1238225"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"Chawla, S., Makarychev, K., Schramm, T., Yaroslavtsev, G.: Near optimal LP rounding algorithm for correlationclustering on complete and complete k-partite graphs. In: STOC 2015, pp. 219\u2013228 (2015)","DOI":"10.1145\/2746539.2746604"},{"key":"12_CR11","unstructured":"Cheng, Y., Church, G.M.: Biclustering of expression data. In: Ismb, vol. 8, pp. 93\u2013103 (2000)"},{"key":"12_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/11672142_28","volume-title":"STACS 2006","author":"G Christodoulou","year":"2006","unstructured":"Christodoulou, G., Mirrokni, V.S., Sidiropoulos, A.: Convergence and approximation in potential games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 349\u2013360. Springer, Heidelberg (2006). doi:\n10.1007\/11672142_28"},{"issue":"2","key":"12_CR13","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1016\/j.tcs.2006.05.008","volume":"361","author":"ED Demaine","year":"2006","unstructured":"Demaine, E.D., Emanuel, D., Fiat, A., Immorlica, N.: Correlation clustering in general weighted graphs. Theor. Comput. Sci. 361(2), 172\u2013187 (2006)","journal-title":"Theor. Comput. Sci."},{"key":"12_CR14","doi-asserted-by":"crossref","unstructured":"Fabrikant, A., Papadimitriou, C., Talwar, K.: The complexity of pure Nash equilibria. In: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, pp. 604\u2013612. ACM (2004)","DOI":"10.1145\/1007352.1007445"},{"issue":"04","key":"12_CR15","doi-asserted-by":"crossref","first-page":"863","DOI":"10.1142\/S0218213004001867","volume":"13","author":"V Filkov","year":"2004","unstructured":"Filkov, V., Skiena, S.: Integrating microarray data by consensus clustering. Int. J. Artif. Intell. Tools 13(04), 863\u2013880 (2004)","journal-title":"Int. J. Artif. Intell. Tools"},{"key":"12_CR16","doi-asserted-by":"crossref","unstructured":"Garg, N., Vazirani, V.V., Yannakakis, M.: Approximate max-flow min-(multi) cut theorems and their applications. In: STOC 1993, pp. 698\u2013707 (1993)","DOI":"10.1145\/167088.167266"},{"issue":"1","key":"12_CR17","doi-asserted-by":"crossref","first-page":"79","DOI":"10.1016\/0022-0000(88)90046-3","volume":"37","author":"DS Johnson","year":"1988","unstructured":"Johnson, D.S., Papadimitriou, C.H., Yannakakis, M.: How easy is local search? J. Comput. Syst. Sci. 37(1), 79\u2013100 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1","key":"12_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1145\/1497577.1497578","volume":"3","author":"HP Kriegel","year":"2009","unstructured":"Kriegel, H.P., Kr\u00f6ger, P., Zimek, A.: Clustering high-dimensional data: a survey on subspace clustering, pattern-based clustering, and correlation clustering. ACM Trans. Knowl. Discov. Data (TKDD) 3(1), 1 (2009)","journal-title":"ACM Trans. Knowl. Discov. Data (TKDD)"},{"issue":"1","key":"12_CR19","doi-asserted-by":"crossref","first-page":"124","DOI":"10.1006\/game.1996.0044","volume":"14","author":"D Monderer","year":"1996","unstructured":"Monderer, D., Shapley, L.S.: Potential games. Games Econ. Behav. 14(1), 124\u2013143 (1996)","journal-title":"Games Econ. Behav."},{"key":"12_CR20","unstructured":"Puleo, G., Milenkovic, O.: Correlation clustering and biclustering with locally bounded errors. In: Proceedings of the 33rd International Conference on Machine Learning, pp. 869\u2013877 (2016)"},{"issue":"1","key":"12_CR21","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/0220004","volume":"20","author":"AA Sch\u00e4ffer","year":"1991","unstructured":"Sch\u00e4ffer, A.A., Yannakakis, M.: Simple local search problems that are hard to solve. SIAM J. Comput. 20(1), 56\u201387 (1991)","journal-title":"SIAM J. Comput."},{"key":"12_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"207","DOI":"10.1007\/978-3-540-27821-4_19","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"Z Svitkina","year":"2004","unstructured":"Svitkina, Z., Tardos, \u00c9.: Min-max multiway cut. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX\/RANDOM -2004. LNCS, vol. 3122, pp. 207\u2013218. Springer, Heidelberg (2004). doi:\n10.1007\/978-3-540-27821-4_19"},{"key":"12_CR23","unstructured":"Swamy, C.: Correlation clustering: maximizing agreements via semidefinite programming. In: SODA 2004, pp. 526\u2013527 (2004)"},{"key":"12_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1007\/978-3-540-77485-3_3","volume-title":"Advances in Web Mining and Web Usage Analysis","author":"P Symeonidis","year":"2007","unstructured":"Symeonidis, P., Nanopoulos, A., Papadopoulos, A., Manolopoulos, Y.: Nearest-biclusters collaborative filtering with constant values. In: Nasraoui, O., Spiliopoulou, M., Srivastava, J., Mobasher, B., Masand, B. (eds.) WebKDD 2006. LNCS, vol. 4811, pp. 36\u201355. Springer, Heidelberg (2007). doi:\n10.1007\/978-3-540-77485-3_3"},{"key":"12_CR25","unstructured":"Van Gael, J., Zhu, X.: Correlation clustering for crosslingual link detection. In: IJCAI, pp. 1744\u20131749 (2007)"},{"key":"12_CR26","first-page":"227","volume-title":"Encyclopedia of Machine Learning","author":"A Wirth","year":"2010","unstructured":"Wirth, A.: Correlation clustering. In: Sammut, C., Webb, G. (eds.) Encyclopedia of Machine Learning, pp. 227\u2013231. Springer, Heidelberg (2010)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-59250-3_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2017,5,23]],"date-time":"2017-05-23T13:07:13Z","timestamp":1495544833000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-59250-3_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319592497","9783319592503"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-59250-3_12","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}