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

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, Markov random fields with efficient approximations, Proceedings. 1998 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (Cat. No.98CB36231), 1998.
DOI : 10.1109/CVPR.1998.698673

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, ICCV, 1999.
DOI : 10.1109/iccv.1999.791245
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.112.6806

C. Chekuri, S. Khanna, J. Naor, and L. Zosin, Approximation algorithms for the metric labeling problem via a new linear programming formulation, SODA, 2001.

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

A. Globerson and T. Jaakkola, Fixing max-product: Convergent message passing algorithms for MAP LP-relaxations, NIPS, 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, Convergent message-passing algorithms for inference over general graphs with convex free energy, UAI, 2008.

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, 2006.
DOI : 10.1109/TPAMI.2006.200

N. Komodakis, N. Paragios, and G. Tziritas, MRF Optimization via Dual Decomposition: Message-Passing Revisited, 2007 IEEE 11th International Conference on Computer Vision, 2007.
DOI : 10.1109/ICCV.2007.4408890

A. Koster, C. Van-hoesel, and A. Kolen, The partial constraint satisfaction problem: Facets and lifting theorems, Operations Research Letters, vol.23, issue.3-5, 1998.
DOI : 10.1016/S0167-6377(98)00043-1

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

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

P. Ravikumar, A. Agarwal, and M. Wainwright, Message-passing for graph-structured linear programs, Proceedings of the 25th international conference on Machine learning, ICML '08, 2008.
DOI : 10.1145/1390156.1390257

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

R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov et al., A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.30, issue.6, 2008.
DOI : 10.1109/TPAMI.2007.70844

D. Tarlow, D. Batra, P. Kohli, and V. Kolmogorov, Dynamic tree block coordinate ascent, ICML, 2011.

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, 2005.
DOI : 10.1109/TIT.2005.856938

Y. Weiss, C. Yanover, and T. Meltzer, MAP estimation, linear programming and belief propagation with convex free energies, UAI, 2007.

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

T. Werner, Revisting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction, 2010.