M. V. Afonso, J. M. Bioucas-dias, and M. A. Figueiredo, An Augmented Lagrangian Approach to the Constrained Optimization Formulation of Imaging Inverse Problems, IEEE Transactions on Image Processing, vol.20, issue.3, pp.681-695, 2011.
DOI : 10.1109/TIP.2010.2076294

A. Archer, J. Fakcharoenphol, C. Harrelson, R. Krauthgamer, K. Talvar et al., Approximate classification via earthmover metrics, SODA, 2004.

Y. Bartal, On approximating arbitrary metrices by tree metrics, Proceedings of the thirtieth annual ACM symposium on Theory of computing , STOC '98, 1998.
DOI : 10.1145/276698.276725

Y. Boykov and V. Kolmogorov, An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision, 2004.

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, pp.1222-1239, 2001.
DOI : 10.1109/iccv.1999.791245

URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

Y. Boykov, O. Veksler, and R. Zabih, A variable window approach to early vision, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.20, issue.12, pp.1283-1294, 1998.
DOI : 10.1109/34.735802

D. Bryant and P. F. Tupper, Hyperconvexity and tight-span theory for diversities, Advances in Mathematics, 2012.
DOI : 10.1016/j.aim.2012.08.008

C. Chekuri, S. Khanna, J. Naor, and L. Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, 12 th Annual ACM-SIAM Symposium on Discrete Algorithms, pp.109-118, 2001.

D. Comaniciu and P. Meer, Mean shift: a robust approach toward feature space analysis, PAMI, 2002.
DOI : 10.1109/34.1000236

A. Delong, L. Gorelick, O. Veksler, and Y. Boykov, Minimizing Energies with Hierarchical Costs, International Journal of Computer Vision, vol.18, issue.9, 2012.
DOI : 10.1007/s11263-012-0531-x

A. Delong, A. Osokin, H. Isack, and Y. Boykov, Fast Approximate Energy Minimization with Label Costs, CVPR, 2010.
DOI : 10.1007/s11263-011-0437-z

P. Dokania and M. P. Kumar, Parsimonious labeing, ICCV, 2015.

J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, Proceedings of the thirty-fifth ACM symposium on Theory of computing , STOC '03, 2003.
DOI : 10.1145/780542.780608

P. Felzenszwalb and D. Huttenlocher, Efficient belief propagation for early vision, Proceedings of the 2004 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 2004. CVPR 2004., 2004.
DOI : 10.1109/CVPR.2004.1315041

M. A. Fischler and R. A. Elschlager, The Representation and Matching of Pictorial Structures, IEEE Transactions on Computers, vol.22, issue.1, pp.67-92, 1973.
DOI : 10.1109/T-C.1973.223602

A. Fix, A. Gruber, E. Boros, and R. Zabih, A graph cut algorithm for high-order Markov random fields, ICCV, 2011.

B. Flach and D. Schlesinger, Transforming an arbitrary minsum problem into a binary one, 2006.

S. Geman and D. Geman, Stochastic relaxation, gibbs distributions, and the bayesian restoration of images, IEEE Trans. Pattern Anal. Mach. Intell, vol.6, issue.6, pp.721-741, 1984.

A. Globerson and T. Jaakkola, Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations, pp.553-560, 2007.

A. Gupta and E. Tardos, A constant factor approximation algorithm for a class of classification problems, Proceedings of the thirty-second annual ACM symposium on Theory of computing , STOC '00, 2000.
DOI : 10.1145/335305.335397

T. Hazan and A. Shashua, Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference, IEEE Transactions on Information Theory, vol.56, issue.12, pp.6294-6316, 2010.
DOI : 10.1109/TIT.2010.2079014

H. Ishikawa, Exact optimization for markov random fields with convex priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.25, issue.10, pp.1333-1336, 2003.
DOI : 10.1109/TPAMI.2003.1233908

S. Jegelka, F. Bach, and S. Sra, Reflection methods for user-friendly submodular optimization, pp.1313-1321, 2013.
URL : https://hal.archives-ouvertes.fr/hal-00905258

V. Jojic, S. Gould, and D. Koller, Fast and smooth: Accelerated dual decomposition for MAP inference, pp.503-510, 2010.

F. Kahl and P. Strandmark, Generalized roof duality, Discrete Applied Mathematics, vol.160, issue.16-17, pp.16-172419, 2012.
DOI : 10.1016/j.dam.2012.06.009

URL : http://dx.doi.org/10.1016/j.dam.2012.06.009

J. Kleinberg and E. Tardos, Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields, STOC, 1999.

V. Kolmogorov, Convergent Tree-Reweighted Message Passing for Energy Minimization, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.28, issue.10, pp.1568-1583, 2006.
DOI : 10.1109/TPAMI.2006.200

V. Kolmogorov, Generalized roof duality and bisubmodular functions, Discrete Applied Mathematics, vol.160, issue.4-5, pp.1144-1152, 2010.
DOI : 10.1016/j.dam.2011.10.026

URL : http://arxiv.org/abs/1005.2305

V. Kolmogorov, Minimizing a sum of submodular functions, Discrete Applied Mathematics, 2012.
DOI : 10.1016/j.dam.2012.05.025

V. Kolmogorov and R. Zabih, What energy functions can be minimized via graph cuts?, pp.147-159, 2004.

N. Komodakis and N. Paragios, Beyond Loose LP-Relaxations: Optimizing MRFs by Repairing Cycles, pp.806-820, 2008.
DOI : 10.1007/978-3-540-88690-7_60

URL : https://hal.archives-ouvertes.fr/hal-00918715

N. Komodakis and N. Paragios, Beyond pairwise energies: Efficient optimization for higher-order MRFs, 2009 IEEE Conference on Computer Vision and Pattern Recognition, pp.2985-2992, 2009.
DOI : 10.1109/CVPR.2009.5206846

N. Komodakis, N. Paragios, and G. Tziritas, MRF Energy Minimization and Beyond via Dual Decomposition, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.33, issue.3, pp.531-552, 2011.
DOI : 10.1109/TPAMI.2010.108

URL : https://hal.archives-ouvertes.fr/hal-00856311

N. Komodakis and G. Tziritas, Approximate Labeling via Graph Cuts Based on Linear Programming, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.8, pp.1436-1453, 2007.
DOI : 10.1109/TPAMI.2007.1061

N. Komodakis, G. Tziritas, and N. Paragios, Performance vs computational efficiency for optimizing single and dynamic MRFs: Setting the state of the art with primal-dual strategies, Computer Vision and Image Understanding, vol.112, issue.1, pp.14-29, 2008.
DOI : 10.1016/j.cviu.2008.06.007

URL : https://hal.archives-ouvertes.fr/hal-00918699

M. P. Kumar, Rounding-based moves for metric labeling, NIPS, 2014.
URL : https://hal.archives-ouvertes.fr/hal-01069910

M. P. Kumar and D. Koller, MAP estimation of semi-metric MRFs via hierarchical graph cuts, UAI, 2009.

M. P. Kumar, V. Kolmogorov, and P. Torr, An analysis of convex relaxations for MAP estimation, NIPS, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00773608

M. P. Kumar and P. Torr, Improved moves for truncated convex models, NIPS, 2008.

L. Ladicky, C. Russell, P. Kohli, and P. Torr, Inference methods for CRFs with co-occurence statistics, 2013.

T. Larsson, M. Patriksson, and A. Stromberg, Ergodic, primal convergence in dual subgradient schemes for convex programming, Mathematical Programming, pp.283-312, 1999.
DOI : 10.1007/s101070050090

R. Manokaran, J. Naor, P. Raghavendra, and R. Schwartz, Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, 2008.
DOI : 10.1145/1374376.1374379

K. Murphy, Y. Weiss, and M. Jordan, Loopy belief propagation for approximate inference: An empirical study, UAI, pp.467-476, 1999.

A. Nedic and D. P. Bertsekas, Incremental Subgradient Methods for Nondifferentiable Optimization, SIAM Journal on Optimization, vol.12, issue.1, pp.109-138, 2001.
DOI : 10.1137/S1052623499362111

A. Nedic and A. Ozdaglar, Approximate Primal Solutions and Rate Analysis for Dual Subgradient Methods, SIAM Journal on Optimization, vol.19, issue.4, pp.1757-1780, 2009.
DOI : 10.1137/070708111

A. Osokin, D. Vetrov, and V. Kolmogorov, Submodular decomposition framework for inference in associative Markov networks with global constraints, CVPR 2011, pp.1889-1896, 2011.
DOI : 10.1109/CVPR.2011.5995361

C. H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Englewoods Cliffs, N.J, 1982.

J. Pearl, Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, 1988.

R. B. Potts, Some generalized order-disorder transformations, Cambridge Philosophical Society, 1952.
DOI : 10.1103/PhysRev.60.252

B. Savchynskyy, J. H. Kappes, S. Schmidt, and C. Schnörr, A study of Nesterov's scheme for Lagrangian decomposition and MAP labeling, CVPR 2011, pp.1817-1823, 2011.
DOI : 10.1109/CVPR.2011.5995652

B. Savchynskyy, S. Schmidt, J. H. Kappes, and C. Schnörr, Efficient MRF energy minimization via adaptive diminishing smoothing, pp.746-755

M. Schlesinger, Syntactic analysis of two-dimensional visual signals in noisy conditions, Kibernetika, 1976.

N. N. Schraudolph, Polynomial-time exact inference in NP-hard binary MRFs via reweighted perfect matching, 13-th International Conference on Artificial Intelligence and Statistics (AISTATS), pp.717-724, 2010.

H. D. Sherali and G. Choi, Recovery of primal solutions when using subgradient optimization methods to solve Lagrangian duals of linear programs, Operations Research Letters, vol.19, issue.3, pp.105-113, 1996.
DOI : 10.1016/0167-6377(96)00019-3

N. Z. Shor, Minimization methods for nondifferentiable functions, 1985.

D. Sontag, T. Meltzer, A. Globerson, Y. Weiss, and T. Jaakkola, Tightening LP relaxations for MAP using message passing, pp.656-664, 2008.

V. V. Vazirani, Approximation Algorithms, 2001.
DOI : 10.1007/978-3-662-04565-7

O. Veksler, Efficient graph-based energy minimization methods in computer vision, 1999.

O. Veksler, Graph Cut Based Optimization for MRFs with Truncated Convex Priors, 2007 IEEE Conference on Computer Vision and Pattern Recognition, 2007.
DOI : 10.1109/CVPR.2007.383249

M. Wainwright, T. Jaakkola, and A. Willsky, MAP Estimation Via Agreement on Trees: Message-Passing and Linear Programming, IEEE Transactions on Information Theory, vol.51, issue.11, pp.3697-3717, 2005.
DOI : 10.1109/TIT.2005.856938

C. Wang, N. Komodakis, and N. Paragios, Markov Random Field modeling, inference & learning in computer vision & image understanding: A survey, Computer Vision and Image Understanding, vol.117, issue.11, pp.1610-1627, 2013.
DOI : 10.1016/j.cviu.2013.07.004

URL : https://hal.archives-ouvertes.fr/hal-00858390

Y. Weiss and W. Freeman, On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs, IEEE Transactions on Information Theory, vol.47, issue.2, pp.723-735, 2001.
DOI : 10.1109/18.910585

T. Werner, A Linear Programming Approach to Max-Sum Problem: A Review, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.29, issue.7, pp.1165-1179, 2007.
DOI : 10.1109/TPAMI.2007.1036

C. Yanover, T. T. Meltzer, and Y. Weiss, Linear programming relaxations and belief propagation ? an empirical study, pp.1887-1907, 2006.

J. Yarkony, R. Morshed, A. T. Ihler, and C. Fowlkes, Tightening MRF relaxations with planar subproblems, pp.770-777, 2011.

.. Moves-for-high-order-potentials, 23 3.6.2 P n Potts model, p.35