{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T19:40:02Z","timestamp":1749584402751,"version":"3.41.0"},"publisher-location":"Cham","reference-count":72,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319464749"},{"type":"electronic","value":"9783319464756"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","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":[[2016]]},"DOI":"10.1007\/978-3-319-46475-6_51","type":"book-chapter","created":{"date-parts":[[2016,9,16]],"date-time":"2016-09-16T08:48:10Z","timestamp":1474015690000},"page":"834-852","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Complexity of Discrete Energy Minimization Problems"],"prefix":"10.1007","author":[{"given":"Mengtian","family":"Li","sequence":"first","affiliation":[]},{"given":"Alexander","family":"Shekhovtsov","sequence":"additional","affiliation":[]},{"given":"Daniel","family":"Huber","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,9,17]]},"reference":[{"unstructured":"The Probabilistic Inference Challenge (2011). http:\/\/www.cs.huji.ac.il\/project\/PASCAL\/","key":"51_CR1"},{"issue":"1","key":"51_CR2","doi-asserted-by":"publisher","first-page":"21","DOI":"10.1016\/S0004-3702(98)00043-5","volume":"102","author":"A Abdelbar","year":"1998","unstructured":"Abdelbar, A., Hedetniemi, S.: Approximating MAPs for belief networks is NP-hard and other theorems. Artif. Intell. 102(1), 21\u201338 (1998)","journal-title":"Artif. Intell."},{"key":"51_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1007\/978-3-642-33715-4_2","volume-title":"Computer Vision \u2013 ECCV 2012","author":"C Arora","year":"2012","unstructured":"Arora, C., Banerjee, S., Kalra, P., Maheshwari, S.N.: Generic cuts: an efficient algorithm for optimal inference in higher order MRF-MAP. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012, Part V. LNCS, vol. 7576, pp. 17\u201330. Springer, Heidelberg (2012)"},{"key":"51_CR4","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-58412-1","volume-title":"Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties","author":"G Ausiello","year":"1999","unstructured":"Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., Protasi, M.: Complexity and Approximation: Combinatorial Optimization Problems and Their Approximability Properties. Springer, Heidelberg (1999)"},{"unstructured":"Bach, S.H., Huang, B., Getoor, L.: Unifying local consistency and MAX SAT relaxations for scalable inference with rounding guarantees. In: AISTATS, JMLR Proceedings, vol. 38 (2015)","key":"51_CR5"},{"unstructured":"Bach, S.H., Huang, B., Getoor, L.: Unifying local consistency and MAX SAT relaxations for scalable inference with rounding guarantees. In: AISTATS, pp. 46\u201355 (2015)","key":"51_CR6"},{"doi-asserted-by":"crossref","unstructured":"Bar-Yehuda, R., Even, S.: On approximating a vertex cover for planar graphs. In: Proceedings of 14th Annual ACM Symposium on Theory of Computing, pp. 303\u2013309 (1982)","key":"51_CR7","DOI":"10.1145\/800070.802205"},{"doi-asserted-by":"crossref","unstructured":"Barbu, A.: Learning real-time MRF inference for image denoising. In: CVPR, pp. 1574\u20131581 (2009)","key":"51_CR8","DOI":"10.1109\/CVPR.2009.5206811"},{"doi-asserted-by":"crossref","unstructured":"Batra, D., Gallagher, A.C., Parikh, D., Chen, T.: Beyond trees: MRF inference via outer-planar decomposition. In: CVPR, pp. 2496\u20132503 (2010)","key":"51_CR9","DOI":"10.1109\/CVPR.2010.5539951"},{"unstructured":"Boros, E., Hammer, P.L., Sun, X.: Network flows and minimization of quadratic pseudo-Boolean functions. Technical report RRR 17\u20131991, RUTCOR, May 1991","key":"51_CR10"},{"unstructured":"Boros, E., Hammer, P.: Pseudo-Boolean optimization. Technical report, RUTCOR, October 2001","key":"51_CR11"},{"issue":"123","key":"51_CR12","doi-asserted-by":"publisher","first-page":"155","DOI":"10.1016\/S0166-218X(01)00341-9","volume":"1\u20133","author":"E Boros","year":"2002","unstructured":"Boros, E., Hammer, P.: Pseudo-Boolean optimization. Discret. Appl. Math. 1\u20133(123), 155\u2013225 (2002)","journal-title":"Discret. Appl. Math."},{"key":"51_CR13","doi-asserted-by":"publisher","first-page":"1222","DOI":"10.1109\/34.969114","volume":"23","author":"Y Boykov","year":"2001","unstructured":"Boykov, Y., Veksler, O., Zabih, R.: Fast approximate energy minimization via graph cuts. PAMI 23, 1222\u20131239 (2001)","journal-title":"PAMI"},{"issue":"3","key":"51_CR14","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1137\/S0895480101396937","volume":"18","author":"C Chekuri","year":"2005","unstructured":"Chekuri, C., Khanna, S., Naor, J., Zosin, L.: A linear programming formulation and approximation algorithms for the metric labeling problem. SIAM J. Discret. Math. 18(3), 608\u2013625 (2005)","journal-title":"SIAM J. Discret. Math."},{"unstructured":"Chekuri, C., Khanna, S., Naor, J., Zosin, L.: Approximation algorithms for the metric labeling problem via a new linear programming formulation. In: Symposium on Discrete Algorithms, pp. 109\u2013118 (2001)","key":"51_CR15"},{"key":"51_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1007\/978-3-540-30201-8_18","volume-title":"Principles and Practice of Constraint Programming \u2013 CP 2004","author":"D Cohen","year":"2004","unstructured":"Cohen, D., Cooper, M., Jeavons, P.G.: A complete characterization of complexity for Boolean constraint optimization problems. In: Wallace, M. (ed.) CP 2004. LNCS, vol. 3258, pp. 212\u2013226. Springer, Heidelberg (2004)"},{"issue":"4","key":"51_CR17","doi-asserted-by":"publisher","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(4), 864\u2013894 (1994)","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Felzenszwalb, P.F., Veksler, O.: Tiered scene labeling with dynamic programming. In: CVPR, pp. 3097\u20133104 (2010)","key":"51_CR18","DOI":"10.1109\/CVPR.2010.5540067"},{"doi-asserted-by":"crossref","unstructured":"Finley, T., Joachims, T.: Training structural SVMs when exact inference is intractable. In: ICML, pp. 304\u2013311. ACM (2008)","key":"51_CR19","DOI":"10.1145\/1390156.1390195"},{"issue":"3","key":"51_CR20","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1109\/PROC.1973.9030","volume":"61","author":"GD Forney Jr","year":"1973","unstructured":"Forney Jr., G.D.: The Viterbi algorithm. Proc. IEEE 61(3), 268\u2013278 (1973)","journal-title":"Proc. IEEE"},{"key":"51_CR21","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1287\/opre.13.3.388","volume":"13","author":"PL Hammer","year":"1965","unstructured":"Hammer, P.L.: Some network flow problems solved with pseudo-Boolean programming. Oper. Res. 13, 388\u2013399 (1965)","journal-title":"Oper. Res."},{"issue":"4","key":"51_CR22","doi-asserted-by":"publisher","first-page":"686","DOI":"10.1145\/502090.502093","volume":"48","author":"DS Hochbaum","year":"2001","unstructured":"Hochbaum, D.S.: An efficient algorithm for image segmentation, Markov random fields and related problems. J. ACM 48(4), 686\u2013701 (2001)","journal-title":"J. ACM"},{"issue":"10","key":"51_CR23","doi-asserted-by":"publisher","first-page":"1333","DOI":"10.1109\/TPAMI.2003.1233908","volume":"25","author":"H Ishikawa","year":"2003","unstructured":"Ishikawa, H.: Exact optimization for Markov random fields with convex priors. PAMI 25(10), 1333\u20131336 (2003)","journal-title":"PAMI"},{"issue":"6","key":"51_CR24","doi-asserted-by":"publisher","first-page":"1234","DOI":"10.1109\/TPAMI.2010.91","volume":"33","author":"H Ishikawa","year":"2011","unstructured":"Ishikawa, H.: Transformation of general binary MRF minimization to the first-order case. PAMI 33(6), 1234\u20131249 (2011)","journal-title":"PAMI"},{"issue":"113","key":"51_CR25","first-page":"21","volume":"2","author":"P Jeavons","year":"2014","unstructured":"Jeavons, P., Krokhin, A., \u017divn\u1ef3, S., et al.: The complexity of valued constraint satisfaction. Bull. EATCS 2(113), 21\u201355 (2014)","journal-title":"Bull. EATCS"},{"key":"51_CR26","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., et al.: A comparative study of modern inference techniques for structured discrete energy minimization problems. IJCV 115, 155\u2013184 (2015)","journal-title":"IJCV"},{"key":"51_CR27","doi-asserted-by":"crossref","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of Computer Computations","author":"Richard M. Karp","year":"1972","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Proceedings of Symposium on the Complexity of Computer Computations, pp. 85\u2013103 (1972)"},{"issue":"5","key":"51_CR28","doi-asserted-by":"publisher","first-page":"616","DOI":"10.1145\/585265.585268","volume":"49","author":"J Kleinberg","year":"2002","unstructured":"Kleinberg, J., Tardos, E.: Approximation algorithms for classification problems with pairwise relationships: metric labeling and Markov random fields. J. ACM 49(5), 616\u2013639 (2002)","journal-title":"J. ACM"},{"doi-asserted-by":"crossref","unstructured":"Kohli, P., Shekhovtsov, A., Rother, C., Kolmogorov, V., Torr, P.: On partial optimality in multi-label MRFs. In: ICML, pp. 480\u2013487 (2008)","key":"51_CR29","DOI":"10.1145\/1390156.1390217"},{"issue":"2","key":"51_CR30","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabih, R.: What energy functions can be minimized via graph cuts? PAMI 26(2), 147\u2013159 (2004)","journal-title":"PAMI"},{"unstructured":"Kolmogorov, V.: Primal-dual algorithm for convex Markov random fields. Technical report MSR-TR-2005-117, Microsoft Research, Cambridge (2005)","key":"51_CR31"},{"issue":"15","key":"51_CR32","doi-asserted-by":"publisher","first-page":"2246","DOI":"10.1016\/j.dam.2012.05.025","volume":"160","author":"V Kolmogorov","year":"2012","unstructured":"Kolmogorov, V.: Minimizing a sum of submodular functions. Discret. Appl. Math. 160(15), 2246\u20132258 (2012)","journal-title":"Discret. Appl. Math."},{"key":"51_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"625","DOI":"10.1007\/978-3-642-39206-1_53","volume-title":"Automata, Languages, and Programming","author":"V Kolmogorov","year":"2013","unstructured":"Kolmogorov, V.: The power of linear programming for finite-valued CSPs: a constructive characterization. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 625\u2013636. Springer, Heidelberg (2013)"},{"issue":"2","key":"51_CR34","doi-asserted-by":"publisher","first-page":"147","DOI":"10.1109\/TPAMI.2004.1262177","volume":"26","author":"V Kolmogorov","year":"2004","unstructured":"Kolmogorov, V., Zabin, R.: What energy functions can be minimized via graph cuts? PAMI 26(2), 147\u2013159 (2004)","journal-title":"PAMI"},{"doi-asserted-by":"crossref","unstructured":"Komodakis, N., Paragios, N., Tziritas, G.: MRF optimization via dual decomposition: message-passing revisited. In: ICCV, pp. 1\u20138 (2007)","key":"51_CR35","DOI":"10.1109\/ICCV.2007.4408890"},{"key":"51_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"806","DOI":"10.1007\/978-3-540-88690-7_60","volume-title":"Computer Vision \u2013 ECCV 2008","author":"N Komodakis","year":"2008","unstructured":"Komodakis, N., Paragios, N.: Beyond loose LP-relaxations: optimizing MRFs by repairing cycles. In: Forsyth, D., Torr, P., Zisserman, A. (eds.) ECCV 2008, Part III. LNCS, vol. 5304, pp. 806\u2013820. Springer, Heidelberg (2008)"},{"issue":"8","key":"51_CR37","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1109\/TPAMI.2007.1061","volume":"29","author":"N Komodakis","year":"2007","unstructured":"Komodakis, N., Tziritas, G.: Approximate labeling via graph cuts based on linear programming. PAMI 29(8), 1436\u20131453 (2007)","journal-title":"PAMI"},{"unstructured":"Kumar, M.P.: Rounding-based moves for metric labeling. In: NIPS, pp. 109\u2013117 (2014)","key":"51_CR38"},{"key":"51_CR39","first-page":"31","volume":"12","author":"MP Kumar","year":"2011","unstructured":"Kumar, M.P., Veksler, O., Torr, P.H.: Improved moves for truncated convex models. J. Mach. Learn. Res. 12, 31\u201367 (2011)","journal-title":"J. Mach. Learn. Res."},{"issue":"9","key":"51_CR40","doi-asserted-by":"publisher","first-page":"1452","DOI":"10.1016\/j.ijar.2011.08.003","volume":"52","author":"J Kwisthout","year":"2011","unstructured":"Kwisthout, J.: Most probable explanations in Bayesian networks: complexity and tractability. Int. J. Approx. Reason. 52(9), 1452\u20131469 (2011)","journal-title":"Int. J. Approx. Reason."},{"key":"51_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"340","DOI":"10.1007\/978-3-642-39091-3_29","volume-title":"Symbolic and Quantitative Approaches to Reasoning with Uncertainty","author":"J Kwisthout","year":"2013","unstructured":"Kwisthout, J.: Structure approximation of most probable explanations in Bayesian networks. In: van der Gaag, L.C. (ed.) ECSQARU 2013. LNCS, vol. 7958, pp. 340\u2013351. Springer, Heidelberg (2013)"},{"key":"51_CR42","doi-asserted-by":"crossref","first-page":"699","DOI":"10.1613\/jair.4794","volume":"53","author":"J Kwisthout","year":"2015","unstructured":"Kwisthout, J.: Tree-width and the computational complexity of MAP approximations in Bayesian networks. J. Artif. Intell. Res. 53, 699\u2013720 (2015)","journal-title":"J. Artif. Intell. Res."},{"key":"51_CR43","series-title":"No. 17 in Oxford Statistical Science Series","volume-title":"Graphical Models","author":"SL Lauritzen","year":"1998","unstructured":"Lauritzen, S.L.: Graphical Models. No. 17 in Oxford Statistical Science Series. Oxford Science Publications, Oxford (1998)"},{"doi-asserted-by":"crossref","unstructured":"Liu, B., Gould, S., Koller, D.: Single image depth estimation from predicted semantic labels. In: CVPR, pp. 1253\u20131260 (2010)","key":"51_CR44","DOI":"10.1109\/CVPR.2010.5539823"},{"unstructured":"Orponen, P., Mannila, H.: On approximation preserving reductions: complete problems and robust measures. Technical report (1987)","key":"51_CR45"},{"issue":"3","key":"51_CR46","doi-asserted-by":"publisher","first-page":"425","DOI":"10.1016\/0022-0000(91)90023-X","volume":"43","author":"CH Papadimitriou","year":"1991","unstructured":"Papadimitriou, C.H., Yannakakis, M.: Optimization, approximation, and complexity classes. J. Comput. Syst. Sci. 43(3), 425\u2013440 (1991)","journal-title":"J. Comput. Syst. Sci."},{"key":"51_CR47","volume-title":"Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference","author":"J Pearl","year":"1988","unstructured":"Pearl, J.: Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference. Morgan Kaufmann Publishers Inc., Burlington (1988)"},{"key":"51_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/978-3-319-14612-6_5","volume-title":"Energy Minimization Methods in Computer Vision and Pattern Recognition","author":"D Pr\u016f\u0161a","year":"2015","unstructured":"Pr\u016f\u0161a, D., Werner, T.: How hard is the LP relaxation of the potts min-sum labeling problem? In: Tai, X.-C., Bae, E., Chan, T.F., Lysaker, M. (eds.) EMMCVPR 2015. LNCS, vol. 8932, pp. 57\u201370. Springer, Heidelberg (2015)"},{"issue":"4","key":"51_CR49","doi-asserted-by":"publisher","first-page":"898","DOI":"10.1109\/TPAMI.2014.2353626","volume":"37","author":"D Prusa","year":"2015","unstructured":"Prusa, D., Werner, T.: Universality of the local marginal polytope. PAMI 37(4), 898\u2013904 (2015)","journal-title":"PAMI"},{"doi-asserted-by":"crossref","unstructured":"Ramalingam, S., Kohli, P., Alahari, K., Torr, P.H.: Exact inference in multi-label CRFs with higher order cliques. In: CVPR, pp. 1\u20138. IEEE (2008)","key":"51_CR50","DOI":"10.1109\/CVPR.2008.4587401"},{"doi-asserted-by":"crossref","unstructured":"Ren, X., Bo, L., Fox, D.: RGB-(D) scene labeling: Features and algorithms. In: CVPR, pp. 2759\u20132766. IEEE (2012)","key":"51_CR51","DOI":"10.1109\/CVPR.2012.6247999"},{"doi-asserted-by":"crossref","unstructured":"Rother, C., Kolmogorov, V., Lempitsky, V., Szummer, M.: Optimizing binary MRFs via extended roof duality. In: CVPR, pp. 1\u20138 (2007)","key":"51_CR52","DOI":"10.1109\/CVPR.2007.383203"},{"key":"51_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-540-74198-5_3","volume-title":"Energy Minimization Methods in Computer Vision and Pattern Recognition","author":"D Schlesinger","year":"2007","unstructured":"Schlesinger, D.: Exact solution of permuted submodular MinSum problems. In: Yuille, A.L., Zhu, S.-C., Cremers, D., Wang, Y. (eds.) EMMCVPR 2007. LNCS, vol. 4679, pp. 28\u201338. Springer, Heidelberg (2007)"},{"key":"51_CR54","series-title":"Computational Imaging and Vision","doi-asserted-by":"crossref","DOI":"10.1007\/978-94-017-3217-8","volume-title":"Ten Lectures on Statistical and Structural Pattern Recognition","author":"MI Schlesinger","year":"2002","unstructured":"Schlesinger, M.I., Hlav\u00e1\u010d, V.: Ten Lectures on Statistical and Structural Pattern Recognition. Computational Imaging and Vision, vol. 24. Kluwer Academic Publishers, Dordrecht (2002)"},{"unstructured":"Schraudolph, N.: Polynomial-time exact inference in NP-hard binary MRFs via reweighted perfect matching. In: AISTATS, JMLR Proceedings, vol. 9, pp. 717\u2013724 (2010)","key":"51_CR55"},{"key":"51_CR56","doi-asserted-by":"publisher","first-page":"346","DOI":"10.1006\/jctb.2000.1989","volume":"80","author":"A Schrijver","year":"2000","unstructured":"Schrijver, A.: A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Comb. Theor. Ser. B 80, 346\u2013355 (2000). http:\/\/homepages.cwi.nl\/\u00a0lex\/files\/minsubm6.ps","journal-title":"J. Comb. Theor. Ser. B"},{"key":"51_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1007\/978-3-642-33783-3_22","volume-title":"Computer Vision \u2013 ECCV 2012","author":"AG Schwing","year":"2012","unstructured":"Schwing, A.G., Urtasun, R.: Efficient exact inference for 3D indoor scene understanding. In: Fitzgibbon, A., Lazebnik, S., Perona, P., Sato, Y., Schmid, C. (eds.) ECCV 2012, Part VI. LNCS, vol. 7577, pp. 299\u2013313. Springer, Heidelberg (2012)"},{"doi-asserted-by":"crossref","unstructured":"Shekhovtsov, A., Swoboda, P., Savchynskyy, B.: Maximum persistency via iterative relaxed inference with graphical models. In: CVPR (2015)","key":"51_CR58","DOI":"10.1109\/CVPR.2015.7298650"},{"doi-asserted-by":"crossref","unstructured":"Shekhovtsov, A., Kohli, P., Rother, C.: Curvature prior for MRF-based segmentation and shape inpainting. In: DAGM\/OAGM, pp. 41\u201351 (2012)","key":"51_CR59","DOI":"10.1007\/978-3-642-32717-9_5"},{"issue":"5","key":"51_CR60","doi-asserted-by":"publisher","first-page":"694","DOI":"10.1109\/12.53581","volume":"39","author":"WK Shih","year":"1990","unstructured":"Shih, W.K., Wu, S., Kuo, Y.S.: Unifying maximum cut and minimum cut of a planar graph. IEEE Trans. Comput. 39(5), 694\u2013697 (1990)","journal-title":"IEEE Trans. Comput."},{"unstructured":"Sontag, D., Choe, D.K., Li, Y.: Efficiently searching for frustrated cycles in MAP inference. In: Uncertainty in Artificial Intelligence (UAI), pp. 795\u2013804 (2012)","key":"51_CR61"},{"issue":"6","key":"51_CR62","doi-asserted-by":"publisher","first-page":"1068","DOI":"10.1109\/TPAMI.2007.70844","volume":"30","author":"R Szeliski","year":"2008","unstructured":"Szeliski, R., Zabih, R., Scharstein, D., Veksler, O., Kolmogorov, V., Agarwala, A., Tappen, M., Rother, C.: A comparative study of energy minimization methods for Markov random fields with smoothness-based priors. PAMI 30(6), 1068\u20131080 (2008)","journal-title":"PAMI"},{"doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S.: The power of linear programming for valued CSPs. In: Symposium on Foundations of Computer Science (FOCS), pp. 669\u2013678 (2012)","key":"51_CR63","DOI":"10.1109\/FOCS.2012.25"},{"doi-asserted-by":"crossref","unstructured":"Thapper, J., \u017divn\u00fd, S.: The complexity of finite-valued CSPs. In: Symposium on the Theory of Computing (STOC), pp. 695\u2013704 (2013)","key":"51_CR64","DOI":"10.1145\/2488608.2488697"},{"issue":"2","key":"51_CR65","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1287\/opre.26.2.305","volume":"26","author":"DM Topkis","year":"1978","unstructured":"Topkis, D.M.: Minimizing a submodular function on a lattice. Oper. Res. 26(2), 305\u2013321 (1978)","journal-title":"Oper. Res."},{"doi-asserted-by":"crossref","unstructured":"Veksler, O.: Graph cut based optimization for MRFs with truncated convex priors. In: CVPR, pp. 1\u20138 (2007)","key":"51_CR66","DOI":"10.1109\/CVPR.2007.383249"},{"doi-asserted-by":"crossref","unstructured":"Vineet, V., Warrell, J., Torr, P.H.S.: A tiered move-making algorithm for general pairwise MRFs. In: CVPR, pp. 1632\u20131639 (2012)","key":"51_CR67","DOI":"10.1109\/CVPR.2012.6247856"},{"issue":"15","key":"51_CR68","doi-asserted-by":"publisher","first-page":"3347","DOI":"10.1016\/j.dam.2009.07.001","volume":"157","author":"S \u017divn\u00fd","year":"2009","unstructured":"\u017divn\u00fd, S., Cohen, D.A., Jeavons, P.G.: The expressive power of binary submodular functions. Discret. Appl. Math. 157(15), 3347\u20133358 (2009)","journal-title":"Discret. Appl. Math."},{"issue":"7","key":"51_CR69","doi-asserted-by":"publisher","first-page":"1165","DOI":"10.1109\/TPAMI.2007.1036","volume":"29","author":"T Werner","year":"2007","unstructured":"Werner, T.: A linear programming approach to max-sum problem: a review. PAMI 29(7), 1165\u20131179 (2007)","journal-title":"PAMI"},{"issue":"9","key":"51_CR70","doi-asserted-by":"publisher","first-page":"1744","DOI":"10.1109\/TPAMI.2011.236","volume":"34","author":"L Xu","year":"2012","unstructured":"Xu, L., Jia, J., Matsushita, Y.: Motion detail preserving optical flow estimation. PAMI 34(9), 1744\u20131757 (2012)","journal-title":"PAMI"},{"doi-asserted-by":"crossref","unstructured":"Yang, Y., Ramanan, D.: Articulated pose estimation with flexible mixtures-of-parts. In: CVPR, pp. 1385\u20131392 (2011)","key":"51_CR71","DOI":"10.1109\/CVPR.2011.5995741"},{"key":"51_CR72","volume-title":"The Power of LP Relaxation for MAP Inference","author":"S \u017divn\u00fd","year":"2014","unstructured":"\u017divn\u00fd, S., Werner, T., Pr\u016f\u0161a, D.A.: The Power of LP Relaxation for MAP Inference. The MIT Press, Cambridge (2014)"}],"container-title":["Lecture Notes in Computer Science","Computer Vision \u2013 ECCV 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-46475-6_51","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T19:15:14Z","timestamp":1749582914000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-46475-6_51"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319464749","9783319464756"],"references-count":72,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-46475-6_51","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"17 September 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ECCV","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Computer Vision","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Amsterdam","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"The Netherlands","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 October 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 October 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eccv2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.eccv2016.org\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}