{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T06:49:00Z","timestamp":1758264540375,"version":"3.40.3"},"publisher-location":"Cham","reference-count":39,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319667089"},{"type":"electronic","value":"9783319667096"}],"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":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-66709-6_9","type":"book-chapter","created":{"date-parts":[[2017,8,14]],"date-time":"2017-08-14T00:13:01Z","timestamp":1502669581000},"page":"103-114","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":12,"title":["A Comparative Study of Local Search Algorithms for Correlation Clustering"],"prefix":"10.1007","author":[{"given":"Evgeny","family":"Levinkov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Alexander","family":"Kirillov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Bjoern","family":"Andres","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,8,15]]},"reference":[{"issue":"10","key":"9_CR1","doi-asserted-by":"crossref","first-page":"1966","DOI":"10.1109\/TPAMI.2011.280","volume":"34","author":"A Alush","year":"2012","unstructured":"Alush, A., Goldberger, J.: Ensemble segmentation using efficient integer linear programming. TPAMI 34(10), 1966\u20131977 (2012)","journal-title":"TPAMI"},{"issue":"99","key":"9_CR2","first-page":"1","volume":"PP","author":"A Alush","year":"2015","unstructured":"Alush, A., Goldberger, J.: Hierarchical image segmentation using correlation clustering. IEEE Trans. Neural Netw. Learn. Syst. PP(99), 1\u201310 (2015)","journal-title":"IEEE Trans. Neural Netw. Learn. Syst."},{"key":"9_CR3","doi-asserted-by":"crossref","unstructured":"Andres, B., Kappes, J.H., Beier, T., K\u00f6the, U., Hamprecht, F.A.: Probabilistic image segmentation with closedness constraints. In: ICCV (2011)","DOI":"10.1109\/ICCV.2011.6126550"},{"key":"9_CR4","doi-asserted-by":"crossref","unstructured":"Andres, B., Kr\u00f6ger, T., Briggman, K.L., Denk, W., Korogod, N., Knott, G., K\u00f6the, U., Hamprecht, F.A.: Globally optimal closed-surface segmentation for connectomics. In: ECCV (2012)","DOI":"10.1007\/978-3-642-33712-3_56"},{"key":"9_CR5","unstructured":"Bachrach, Y., Kohli, P., Kolmogorov, V., Zadimoghaddam, M.: Optimal coalition structure generation in cooperative graph games. In: AAAI (2013). http:\/\/www.aaai.org\/ocs\/index.php\/AAAI\/AAAI13\/paper\/view\/6407\/7071"},{"key":"9_CR6","unstructured":"Bagon, S., Galun, M.: Large scale correlation clustering optimization. CoRR abs\/1112.2903 (2011). http:\/\/arxiv.org\/abs\/1112.2903"},{"issue":"1\u20133","key":"9_CR7","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."},{"key":"9_CR8","doi-asserted-by":"crossref","unstructured":"Beier, T., Hamprecht, F.A., Kappes, J.H.: Fusion moves for correlation clustering. In: CVPR (2015)","DOI":"10.1109\/CVPR.2015.7298973"},{"key":"9_CR9","doi-asserted-by":"crossref","unstructured":"Beier, T., Kr\u00f6ger, T., Kappes, J.H., K\u00f6the, U., Hamprecht, F.A.: Cut, Glue & Cut: a fast, approximate solver for multicut partitioning. In: CVPR (2014)","DOI":"10.1109\/CVPR.2014.17"},{"issue":"3","key":"9_CR10","doi-asserted-by":"crossref","first-page":"360","DOI":"10.1016\/j.jcss.2004.10.012","volume":"71","author":"M Charikar","year":"2005","unstructured":"Charikar, M., Guruswami, V., Wirth, A.: Clustering with qualitative information. J. Comput. Syst. Sci. 71(3), 360\u2013383 (2005)","journal-title":"J. Comput. Syst. Sci."},{"issue":"1\u20133","key":"9_CR11","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.: The partition problem. Math. Program. 59(1\u20133), 87\u2013115 (1993)","journal-title":"Math. Program."},{"key":"9_CR12","doi-asserted-by":"crossref","first-page":"864","DOI":"10.1137\/S0097539792225297","volume":"23","author":"E Dahlhaus","year":"1994","unstructured":"Dahlhaus, E., Johnson, D.S., Papadimitriou, C.H., Seymour, P.D., Yannakakis, M.: The complexity of multiterminal cuts. SIAM J. Comput. 23, 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"issue":"2\u20133","key":"9_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. Theoret. Comput. Sci. 361(2\u20133), 172\u2013187 (2006)","journal-title":"Theoret. Comput. Sci."},{"issue":"1","key":"9_CR14","doi-asserted-by":"crossref","first-page":"24","DOI":"10.1287\/moor.19.1.24","volume":"19","author":"O Goldschmidt","year":"1994","unstructured":"Goldschmidt, O., Hochbaum, D.S.: A polynomial algorithm for the k-cut problem for fixed k. Math. Oper. Res. 19(1), 24\u201337 (1994)","journal-title":"Math. Oper. Res."},{"issue":"1","key":"9_CR15","doi-asserted-by":"crossref","first-page":"59","DOI":"10.1007\/BF01589097","volume":"45","author":"M Gr\u00f6tschel","year":"1989","unstructured":"Gr\u00f6tschel, M., Wakabayashi, Y.: A cutting plane algorithm for a clustering problem. Math. Program. 45(1), 59\u201396 (1989)","journal-title":"Math. Program."},{"key":"9_CR16","unstructured":"Hor\u0148\u00e1kov\u00e1, A., Lange, J.H., Andres, B.: Analysis and optimization of graph decompositions by lifted multicuts. In: ICML (Forthcoming) (2017)"},{"key":"9_CR17","unstructured":"Jia, Y., Shelhamer, E., Donahue, J., Karayev, S., Long, J., Girshick, R., Guadarrama, S., Darrell, T.: Caffe: convolutional architecture for fast feature embedding (2014). arXiv preprint arXiv:1408.5093"},{"issue":"2","key":"9_CR18","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1007\/s11263-015-0809-x","volume":"115","author":"JH Kappes","year":"2015","unstructured":"Kappes, J.H., Andres, B., Hamprecht, F.A., Schn\u00f6rr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B.X., Kr\u00f6ger, T., Lellmann, J., Komodakis, N., Savchynskyy, B., Rother, C.: A comparative study of modern inference techniques for structured discrete energy minimization problems. Int. J. Comput. Vis. 115(2), 155\u2013184 (2015)","journal-title":"Int. J. Comput. Vis."},{"key":"9_CR19","doi-asserted-by":"crossref","unstructured":"Kappes, J.H., Speth, M., Andres, B., Reinelt, G., Schn\u00f6rr, C.: Globally optimal image partitioning by multicuts. In: EMMCVPR (2011)","DOI":"10.1007\/978-3-642-23094-3_3"},{"key":"9_CR20","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.cviu.2015.11.005","volume":"143","author":"JH Kappes","year":"2015","unstructured":"Kappes, J.H., Speth, M., Reinelt, G., Schn\u00f6rr, C.: Higher-order segmentation via multicuts. Comput. Vis. Image Underst. 143, 104\u2013119 (2015)","journal-title":"Comput. Vis. Image Underst."},{"key":"9_CR21","doi-asserted-by":"crossref","unstructured":"Kappes, J.H., Swoboda, P., Savchynskyy, B., Hazan, T., Schn\u00f6rr, C.: Probabilistic correlation clustering and image partitioning using perturbed multicuts. In: Scale Space and Variational Methods in Computer Vision (2015)","DOI":"10.1007\/978-3-319-18461-6_19"},{"key":"9_CR22","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"BW Kernighan","year":"1970","unstructured":"Kernighan, B.W., Lin, S.: An efficient heuristic procedure for partitioning graphs. Bell Syst. Tech. J. 49, 291\u2013307 (1970)","journal-title":"Bell Syst. Tech. J."},{"key":"9_CR23","doi-asserted-by":"crossref","unstructured":"Keuper, M., Andres, B., Brox, T.: Motion trajectory segmentation via minimum cost multicuts. In: ICCV (2015)","DOI":"10.1109\/ICCV.2015.374"},{"key":"9_CR24","doi-asserted-by":"crossref","unstructured":"Keuper, M., Levinkov, E., Bonneel, N., Lavou\u00e9, G., Brox, T., Andres, B.: Efficient decomposition of image and mesh graphs by lifted multicuts. In: International Conference on Computer Vision (2015)","DOI":"10.1109\/ICCV.2015.204"},{"key":"9_CR25","unstructured":"Kim, S., Nowozin, S., Kohli, P., Yoo, C.: Higher-order correlation clustering for image segmentation. In: NIPS (2011)"},{"key":"9_CR26","doi-asserted-by":"crossref","first-page":"1761","DOI":"10.1109\/TPAMI.2014.2303095","volume":"36","author":"S Kim","year":"2014","unstructured":"Kim, S., Yoo, C., Nowozin, S., Kohli, P.: Image segmentation using higher-order correlation clustering. TPAMI 36, 1761\u20131774 (2014)","journal-title":"TPAMI"},{"key":"9_CR27","series-title":"Leibniz International Proceedings in Informatics","first-page":"554","volume-title":"32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)","author":"PN Klein","year":"2015","unstructured":"Klein, P.N., Mathieu, C., Zhou, H.: Correlation clustering and two-edge-connected augmentation for planar graphs. In: Mayr, E.W., Ollinger, N. (eds.) 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics, vol. 30, pp. 554\u2013567. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl (2015)"},{"issue":"12","key":"9_CR28","doi-asserted-by":"crossref","first-page":"2959","DOI":"10.1523\/JNEUROSCI.3189-07.2008","volume":"28","author":"G Knott","year":"2008","unstructured":"Knott, G., Marchman, H., Wall, D., Lich, B.: Serial section scanning electron microscopy of adult brain tissue using focused ion beam milling. J. Neurosci. 28(12), 2959\u20132964 (2008)","journal-title":"J. Neurosci."},{"issue":"11","key":"9_CR29","doi-asserted-by":"crossref","first-page":"2278","DOI":"10.1109\/5.726791","volume":"86","author":"Y LeCun","year":"1998","unstructured":"LeCun, Y., Bottou, L., Bengio, Y., Haffner, P.: Gradient-based learning applied to document recognition. Proc. IEEE 86(11), 2278\u20132324 (1998)","journal-title":"Proc. IEEE"},{"key":"9_CR30","unstructured":"Lecun, Y., Cortes, C.: The MNIST database of handwritten digits. http:\/\/yann.lecun.com\/exdb\/mnist\/"},{"key":"9_CR31","doi-asserted-by":"crossref","unstructured":"Leskovec, J., Huttenlocher, D., Kleinberg, J.: Signed networks in social media. In: CHI (2010)","DOI":"10.1145\/1753326.1753532"},{"key":"9_CR32","doi-asserted-by":"crossref","unstructured":"Martin, D., Fowlkes, C., Tal, D., Malik, J.: A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In: Proceedings of the 8th International Conference on Computer Vision, vol. 2, pp. 416\u2013423, July 2001","DOI":"10.1109\/ICCV.2001.937655"},{"issue":"5","key":"9_CR33","doi-asserted-by":"crossref","first-page":"873","DOI":"10.1016\/j.jmva.2006.11.013","volume":"98","author":"M Meil\u0103","year":"2007","unstructured":"Meil\u0103, M.: Comparing clusterings\u2013an information based distance. J. Multivar. Anal. 98(5), 873\u2013895 (2007)","journal-title":"J. Multivar. Anal."},{"key":"9_CR34","doi-asserted-by":"crossref","unstructured":"Nowozin, S., Jegelka, S.: Solution stability in linear programming relaxations: graph partitioning and unsupervised learning. In: ICML (2009)","DOI":"10.1145\/1553374.1553473"},{"key":"9_CR35","doi-asserted-by":"crossref","unstructured":"Rother, C., Kolmogorov, V., Lempitsky, V., Szummer, M.: Optimizing binary MRFs via extended roof duality. In: CVPR (2007)","DOI":"10.1109\/CVPR.2007.383203"},{"key":"9_CR36","unstructured":"Schraudolph, N.N., Kamenetsky, D.: Efficient exact inference in planar ising models. In: NIPS (2009)"},{"key":"9_CR37","doi-asserted-by":"crossref","first-page":"165","DOI":"10.1613\/jair.3715","volume":"45","author":"T Voice","year":"2012","unstructured":"Voice, T., Polukarov, M., Jennings, N.R.: Coalition structure generation over graphs. J. Artif. Intell. Res. 45, 165\u2013196 (2012)","journal-title":"J. Artif. Intell. Res."},{"key":"9_CR38","unstructured":"Yarkony, J.: Analyzing PlanarCC: demonstrating the equivalence of PlanarCC and the multi-cut LP relaxation. In: NIPS Workshop on Discrete Optimization (2014)"},{"key":"9_CR39","doi-asserted-by":"crossref","unstructured":"Yarkony, J., Ihler, A., Fowlkes, C.C.: Fast planar correlation clustering for image segmentation. In: ECCV (2012)","DOI":"10.1007\/978-3-642-33783-3_41"}],"container-title":["Lecture Notes in Computer Science","Pattern Recognition"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-66709-6_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,10,2]],"date-time":"2019-10-02T06:50:06Z","timestamp":1569999006000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-66709-6_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319667089","9783319667096"],"references-count":39,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-66709-6_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]}}}