{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,22]],"date-time":"2026-09-22T17:04:26Z","timestamp":1790096666910,"version":"4.0.1"},"reference-count":43,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T00:00:00Z","timestamp":1462924800000},"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":["J Math Imaging Vis"],"published-print":{"date-parts":[[2016,10]]},"DOI":"10.1007\/s10851-016-0659-3","type":"journal-article","created":{"date-parts":[[2016,5,11]],"date-time":"2016-05-11T10:38:18Z","timestamp":1462963098000},"page":"221-237","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Multicuts and Perturb & MAP for Probabilistic Graph Clustering"],"prefix":"10.1007","volume":"56","author":[{"given":"J\u00f6rg Hendrik","family":"Kappes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Paul","family":"Swoboda","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bogdan","family":"Savchynskyy","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tamir","family":"Hazan","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christoph","family":"Schn\u00f6rr","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,5,11]]},"reference":[{"key":"659_CR1","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-642-59101-3","volume-title":"Combinatorial Theory","author":"M Aigner","year":"1997","unstructured":"Aigner, M.: Combinatorial Theory. Springer, Berlin (1997)"},{"issue":"8","key":"659_CR2","doi-asserted-by":"crossref","first-page":"999","DOI":"10.1002\/cpa.3160430805","volume":"43","author":"L Ambrosio","year":"1990","unstructured":"Ambrosio, L., Tortorelli, V.: Approximation of functionals depending on jumps by elliptic functionals via $$\\gamma $$ \u03b3 -convergence. Commun. Pure Appl. Math. 43(8), 999\u20131036 (1990)","journal-title":"Commun. Pure Appl. Math."},{"key":"659_CR3","unstructured":"Andres, B., Beier, T., Kappes, J.H.: OpenGM: A C++ library for Discrete Graphical Models. CoRR arXiv:1206.0111 (2012)"},{"key":"659_CR4","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, pp. 2611\u20132618. IEEE (2011)","DOI":"10.1109\/ICCV.2011.6126550"},{"key":"659_CR5","unstructured":"Bagon, S., Galun, M.: Large scale correlation clustering optimization. CoRR arXiv:1112.2903 (2011)"},{"issue":"1\u20133","key":"659_CR6","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":"659_CR7","doi-asserted-by":"crossref","unstructured":"Beier, T., Hamprecht, F.A., Kappes, J.H.: Fusion moves for correlation clustering. In: IEEE Conference on Computer Vision an Pattern Recognition (CVPR) (2015)","DOI":"10.1109\/CVPR.2015.7298973"},{"key":"659_CR8","doi-asserted-by":"crossref","unstructured":"Beier, T., Kroeger, T., Kappes, J.H., Koethe, U., Hamprecht, F.A.: Cut, Glue & cut: a fast, approximate solver for multicut partitioning. In: IEEE Conference on Computer Vision and Pattern Recognition (2014)","DOI":"10.1109\/CVPR.2014.17"},{"key":"659_CR9","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/7132.001.0001","volume-title":"Visual Reconstruction","author":"A Blake","year":"1987","unstructured":"Blake, A., Zisserman, A.: Visual Reconstruction. MIT Press, Massachusetts (1987)"},{"issue":"2","key":"659_CR10","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1109\/TKDE.2007.190689","volume":"20","author":"U Brandes","year":"2008","unstructured":"Brandes, U., Delling, D., Gaertler, M., G\u00f6rke, R., Hoefer, M., Nikoloski, Z., Wagner, D.: On modularity clustering. IEEE Trans. Knowl. Data Eng. 20(2), 172\u2013188 (2008). doi: 10.1109\/TKDE.2007.190689","journal-title":"IEEE Trans. Knowl. Data Eng."},{"issue":"4","key":"659_CR11","doi-asserted-by":"crossref","first-page":"1113","DOI":"10.1137\/110856733","volume":"5","author":"A Chambolle","year":"2012","unstructured":"Chambolle, A., Cremers, D., Pock, T.: A convex approach to minimal partitions. SIAM J. Imaging Sci. 5(4), 1113\u20131158 (2012)","journal-title":"SIAM J. Imaging Sci."},{"issue":"1\u20133","key":"659_CR12","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/BF01581239","volume":"59","author":"S Chopra","year":"1993","unstructured":"Chopra, S., Rao, M.: The partition problem. Math. Programm. 59(1\u20133), 87\u2013115 (1993). doi: 10.1007\/BF01581239","journal-title":"Math. Programm."},{"issue":"2","key":"659_CR13","doi-asserted-by":"publisher","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). doi: 10.1016\/j.tcs.2006.05.008 . Approximation and Online Algorithms","journal-title":"Theor. Comput. Sci."},{"issue":"2","key":"659_CR14","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1007\/BF02579273","volume":"1","author":"M Gr\u00f6tschel","year":"1981","unstructured":"Gr\u00f6tschel, M., Lov\u00e1sz, L., Schrijver, A.: The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1(2), 169\u2013197 (1981)","journal-title":"Combinatorica"},{"key":"659_CR15","series-title":"Applied Mathematics Series","volume-title":"Statistical Theory of Extreme Values and Some Practical Applications: A Series of Lectures","author":"E Gumbel","year":"1954","unstructured":"Gumbel, E.: Statistical Theory of Extreme Values and Some Practical Applications: A Series of Lectures. Applied Mathematics Series. U. S. Government Printing Office, Washington, DC (1954)"},{"key":"659_CR16","unstructured":"Hazan, T., Jaakkola, T.: On the partition function and random maximum a-posteriori perturbations. In: ICML. icml.cc \/ Omnipress (2012)"},{"key":"659_CR17","unstructured":"Hazan, T., Maji, S., Jaakkola, T.S.: On sampling from the Gibbs distribution with random maximum a-posteriori perturbations. In: C.J.C. Burges, L.\u00a0Bottou, Z.\u00a0Ghahramani, K.Q. Weinberger (eds.) Advances in Neural Information Processing Systems 26: 27th Annual Conference on Neural Information Processing Systems 2013. Proceedings of a meeting held December 5\u20138, 2013, Lake Tahoe, Nevada, pp. 1268\u20131276 (2013)"},{"issue":"1","key":"659_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/34.566806","volume":"19","author":"T Hofmann","year":"1997","unstructured":"Hofmann, T., Buhmann, J.: Pairwise data clustering by deterministic annealing. IEEE Trans. Patt. Anal. Mach. Intell. 19(1), 1\u201314 (1997)","journal-title":"IEEE Trans. Patt. Anal. Mach. Intell."},{"issue":"3","key":"659_CR19","doi-asserted-by":"crossref","first-page":"497","DOI":"10.1145\/990308.990313","volume":"51","author":"R Kannan","year":"2004","unstructured":"Kannan, R., Vempala, S., Vetta, A.: On clusterings: good, bad and spectral. J. ACM 51(3), 497\u2013515 (2004)","journal-title":"J. ACM"},{"issue":"2","key":"659_CR20","doi-asserted-by":"publisher","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). doi: 10.1007\/s11263-015-0809-x","journal-title":"Int. J. Comput. Vis."},{"key":"659_CR21","doi-asserted-by":"crossref","unstructured":"Kappes, J.H., Andres, B., Hamprecht, F.A., Schn\u00f6rr, C., Nowozin, S., Batra, D., Kim, S., Kausler, B.X., Lellmann, J., Komodakis, N., Rother, C.: A comparative study of modern inference techniques for discrete energy minimization problems. In: CVPR (2013)","DOI":"10.1109\/CVPR.2013.175"},{"key":"659_CR22","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, pp. 31\u201344. Springer (2011)","DOI":"10.1007\/978-3-642-23094-3_3"},{"key":"659_CR23","doi-asserted-by":"crossref","first-page":"104","DOI":"10.1016\/j.cviu.2015.11.005","volume":"143","author":"JH Kappes","year":"2016","unstructured":"Kappes, J.H., Speth, M., Reinelt, G., Schn\u00f6rr, C.: Higher-order segmentation via multicuts. Comput. Vis. Image Underst. 143, 104\u2013119 (2016). Inference and Learning of Graphical Models Theory and Applications in Computer Vision and Image Analysis","journal-title":"Comput. Vis. Image Underst."},{"issue":"2","key":"659_CR24","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(2), 291\u2013308 (1970)","journal-title":"Bell Syst. Tech. J."},{"key":"659_CR25","doi-asserted-by":"crossref","first-page":"498","DOI":"10.1109\/18.910572","volume":"47","author":"F Kschischang","year":"2001","unstructured":"Kschischang, F., Member, S., Frey, B.J., Loeliger, Ha: Factor graphs and the sum-product algorithm. IEEE Trans. Inf. Theory 47, 498\u2013519 (2001)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"659_CR26","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198522195.001.0001","volume-title":"Graphical Models","author":"SL Lauritzen","year":"1996","unstructured":"Lauritzen, S.L.: Graphical Models. Oxford University Press, Oxford (1996)"},{"issue":"4","key":"659_CR27","doi-asserted-by":"crossref","first-page":"1049","DOI":"10.1137\/100805844","volume":"4","author":"J Lellmann","year":"2011","unstructured":"Lellmann, J., Schn\u00f6rr, C.: Continuous multiclass labeling approaches and algorithms. SIAM J. Imaging Sci. 4(4), 1049\u20131096 (2011)","journal-title":"SIAM J. Imaging Sci."},{"issue":"4","key":"659_CR28","doi-asserted-by":"crossref","first-page":"395","DOI":"10.1007\/s11222-007-9033-z","volume":"17","author":"U Luxburg von","year":"2007","unstructured":"von Luxburg, U.: A Tutorial on Spectral Clustering. Stat. Comput. 17(4), 395\u2013416 (2007)","journal-title":"Stat. Comput."},{"issue":"3","key":"659_CR29","doi-asserted-by":"crossref","first-page":"235","DOI":"10.1561\/2200000008","volume":"2","author":"U Luxburg von","year":"2009","unstructured":"von Luxburg, U.: Clustering stability: an overview. Found. Trends Mach. Learn. 2(3), 235\u2013274 (2009)","journal-title":"Found. Trends Mach. Learn."},{"key":"659_CR30","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 (2001)","DOI":"10.1109\/ICCV.2001.937655"},{"key":"659_CR31","first-page":"2169","volume":"11","author":"JM Mooij","year":"2010","unstructured":"Mooij, J.M.: libDAI: a free and open source C++ library for discrete approximate inference in graphical models. J. Mach. Learn. Res. 11, 2169\u20132173 (2010)","journal-title":"J. Mach. Learn. Res."},{"key":"659_CR32","doi-asserted-by":"crossref","unstructured":"Nowozin, S., Jegelka, S.: Solution stability in linear programming relaxations: graph partitioning and unsupervised learning. In: Danyluk, A.P., Bottou, L., Littman, M.L. (eds.) ICML, ACM International Conference Proceeding Series, vol. 382, pp. 769\u2013776. ACM (2009)","DOI":"10.1145\/1553374.1553473"},{"issue":"1\u20133","key":"659_CR33","doi-asserted-by":"crossref","first-page":"25","DOI":"10.1007\/s11263-007-0061-0","volume":"77","author":"P Orbanz","year":"2008","unstructured":"Orbanz, P., Buhmann, J.: Nonparametric bayesian image segmentation. Int. J. Comput. Vis. 77(1\u20133), 25\u201345 (2008)","journal-title":"Int. J. Comput. Vis."},{"key":"659_CR34","doi-asserted-by":"crossref","unstructured":"Papandreou, G., Yuille, A.: Perturb-and-MAP Random Fields: Using Discrete Optimization to Learn and Sample from Energy Models. In: Proceedings of the ICCV (2011)","DOI":"10.1109\/ICCV.2011.6126242"},{"key":"659_CR35","doi-asserted-by":"crossref","unstructured":"Papandreou, G., Yuille, A.L.: Perturb-and-map random fields: using discrete optimization to learn and sample from energy models. In: Metaxas, D.N., Quan, L., Sanfeliu, A., Gool, L.J.V. (eds.) ICCV, pp. 193\u2013200. IEEE (2011)","DOI":"10.1109\/ICCV.2011.6126242"},{"issue":"2","key":"659_CR36","doi-asserted-by":"crossref","first-page":"190","DOI":"10.1007\/s11263-012-0578-8","volume":"103","author":"T P\u00e4tz","year":"2013","unstructured":"P\u00e4tz, T., Kirby, R., Preusser, T.: Ambrosio-Tortorelli segmentation of stochastic images: model extensions, theoretical investigations and numerical methods. Int. J. Comput. Vis. 103(2), 190\u2013212 (2013)","journal-title":"Int. J. Comput. Vis."},{"key":"659_CR37","series-title":"LNCS","doi-asserted-by":"crossref","first-page":"120","DOI":"10.1007\/978-3-642-39140-8_8","volume-title":"Similarity-Based Pattern Recognition","author":"N Rebagliati","year":"2013","unstructured":"Rebagliati, N., Rota Bulo, S., Pelillo, M.: Correlation clustering with stochastic labellings. In: Pelillo, M. (ed.) Similarity-Based Pattern Recognition. LNCS, vol. 7953, pp. 120\u2013133. Springer, Berlin (2013)"},{"key":"659_CR38","first-page":"185","volume-title":"Advances in Neural Information Processing Systems 16","author":"N Shental","year":"2004","unstructured":"Shental, N., Zomet, A., Hertz, T., Weiss, Y.: Pairwise clustering and graphical models. In: Thrun, S., Saul, L., Sch\u00f6lkopf, B. (eds.) Advances in Neural Information Processing Systems 16, pp. 185\u2013192. MIT Press, Cambridge, MA (2004)"},{"issue":"8","key":"659_CR39","doi-asserted-by":"crossref","first-page":"888","DOI":"10.1109\/34.868688","volume":"22","author":"J Shi","year":"2000","unstructured":"Shi, J., Malik, J.: Normalized cuts and image segmentation. IEEE Trans. Pattern Anal. Mach. Intell. 22(8), 888\u2013905 (2000)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"659_CR40","doi-asserted-by":"crossref","DOI":"10.1201\/9780203014127","volume-title":"Infinite Divisibility of Probability Distributions on the Real Line","author":"F Steutel","year":"2003","unstructured":"Steutel, F., van Harn, K.: Infinite Divisibility of Probability Distributions on the Real Line. Chapman & Hall\/CRC Pure and Applied Mathematics. CRC Press, Boca Raton (2003)"},{"issue":"5","key":"659_CR41","doi-asserted-by":"publisher","first-page":"1120","DOI":"10.1109\/TIT.2003.810642","volume":"49","author":"MJ Wainwright","year":"2003","unstructured":"Wainwright, M.J., Jaakkola, T.S., Willsky, A.S.: Tree-based reparameterization framework for analysis of sum-product and related algorithms. IEEE Trans. Inf. Theory 49(5), 1120\u20131146 (2003). doi: 10.1109\/TIT.2003.810642","journal-title":"IEEE Trans. Inf. Theory"},{"key":"659_CR42","doi-asserted-by":"publisher","unstructured":"Wainwright, M.J., Jordan, M.I.: Graphical models, exponential families, and variational inference. Found. Trends $$\\textregistered $$ \u00ae Mach. Learn. 1, 1\u2013305 (2008). doi: 10.1561\/2200000001","DOI":"10.1561\/2200000001"},{"issue":"7","key":"659_CR43","doi-asserted-by":"publisher","first-page":"2282","DOI":"10.1109\/TIT.2005.850085","volume":"51","author":"JS Yedidia","year":"2005","unstructured":"Yedidia, J.S., Freeman, W., Weiss, Y.: Constructing free-energy approximations and generalized belief propagation algorithms. IEEE Trans. Inf. Theory 51(7), 2282\u20132312 (2005). doi: 10.1109\/TIT.2005.850085","journal-title":"IEEE Trans. Inf. Theory"}],"container-title":["Journal of Mathematical Imaging and Vision"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-016-0659-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10851-016-0659-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10851-016-0659-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,6,16]],"date-time":"2024-06-16T09:32:42Z","timestamp":1718530362000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10851-016-0659-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,5,11]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,10]]}},"alternative-id":["659"],"URL":"https:\/\/doi.org\/10.1007\/s10851-016-0659-3","relation":{},"ISSN":["0924-9907","1573-7683"],"issn-type":[{"value":"0924-9907","type":"print"},{"value":"1573-7683","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,5,11]]}}}