T. Ajanthan, R. Hartley, M. Salzmann, and H. Li, Iteratively reweighted graph cut for multi-label MRFs with non-convex priors, 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2014.
DOI : 10.1109/CVPR.2015.7299150
URL : http://arxiv.org/abs/1411.6340

M. Andrew, M. Hajiaghayi, H. Karloff, and A. Moitra, Capacitated Metric Labeling, SODA, 2011.
DOI : 10.1137/1.9781611973082.76

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.118.3857

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.

P. Dokania and M. P. Kumar, Parsimonious Labeling, 2015 IEEE International Conference on Computer Vision (ICCV), 2015.
DOI : 10.1109/ICCV.2015.205
URL : https://hal.archives-ouvertes.fr/hal-01223973

J. Fakcharoenphol, S. Rao, and K. Talwar, A tight bound on approximating arbitrary metrics by tree metrics, STOC, 2003.
DOI : 10.1145/780542.780608
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.11.2667

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. Kappes, B. Andres, F. Hamprecht, C. Schnoerr, S. Nowozin et al., A Comparative Study of Modern Inference Techniques for Structured Discrete Energy Minimization Problems, International Journal of Computer Vision, vol.15, issue.7, 2015.
DOI : 10.1089/cmb.2007.0158
URL : https://hal.archives-ouvertes.fr/hal-01247122

J. Kleinberg and E. Tardos, Approximation algorithms for classification problems with pairwise relationships: Metric labeling and Markov random fields, STOC, 1999.
DOI : 10.1145/585265.585268
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.31.3602

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.100.2409

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.3345

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, 2008.
DOI : 10.1016/j.cviu.2008.06.007
URL : https://hal.archives-ouvertes.fr/hal-00918699

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
URL : http://digitalarchive.maastrichtuniversity.nl/fedora/get/guid:ba994447-9350-400f-bbe0-9d6557aadee8/ASSET1

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 and P. Torr, Improved moves for truncated convex models, NIPS, 2008.

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

P. Pansari and M. P. Kumar, Truncated max-of-convex models, 2015.

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

H. Racke, Optimal hierarchical decompositions for congestion minimization in networks, Proceedings of the fourtieth annual ACM symposium on Theory of computing, STOC 08, 2008.
DOI : 10.1145/1374376.1374415

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.214.7185

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.9565

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, 2013.
DOI : 10.1016/j.cviu.2013.07.004
URL : https://hal.archives-ouvertes.fr/hal-00858390

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
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.387.2426

T. Werner, Revisting the linear programming relaxation approach to Gibbs energy minimization and weighted constraint satisfaction, 2010.
DOI : 10.1109/tpami.2009.134