S. Boyd and L. Vandenberghe, Convex Optimization, 2004.

Y. Boykov, O. Veksler, and R. Zabih, Fast approximate energy minimization via graph cuts, PAMI, vol.23, issue.11, pp.1222-1239, 2001.
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 labelling problem via a new linear programming formulation, SODA, 2001.

S. Chopra and M. R. Rao, The parition problem, Mathematical Programming, vol.59, pp.87-115, 1993.

F. Cohen, Modeling and Applications of Stochastic Processes, Kluwer, 1986.

E. Dalhaus, D. Johnson, C. Papadimitriou, P. Seymour, and M. Yannakakis, The complexity of multi-terminal cuts, SICOMP, vol.23, issue.4, pp.864-894, 1994.

E. De-klerk, D. Pasechnik, and J. Warners, Approximate graph colouring and max-k-cut algorithms based on the theta function, Journal of Combinatorial Optimization, vol.8, issue.3, pp.267-294, 2004.

M. Goemans and D. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of ACM, vol.42, pp.1115-1145, 1995.

P. Hammer and B. Kalantari, A bound on the roof duality gap, 1987.

P. Hammer, P. Hansen, and B. Simeone, Roof duality, complementation and persistency in quadratic 0-1 optimization, Mathematical Programming, pp.121-155, 1984.

H. Ishikawa, Exact optimization for Markov random fields with convex priors, PAMI, vol.25, issue.10, pp.1333-1336, 2003.
DOI : 10.1109/tpami.2003.1233908
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.106.8689

A. Karzanov, Minimum 0-extension of graph metrics, European Journal of Combinatorics, vol.19, pp.71-101, 1998.

S. Kim and M. Kojima, Second-order cone programming relaxation of nonconvex quadratic optimization problems, 2000.

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

V. Kolmogorov, Convergent tree-reweighted message passing for energy minimization, PAMI, vol.28, issue.10, pp.1568-1583, 2006.

N. Komodakis, N. Paragios, and G. Tziritas, MRF optimization via dual decomposition: Messagepassing revisited, ICCV, 2007.
DOI : 10.1109/iccv.2007.4408890
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.150.3345

A. Koster, C. Van-hoesel, and A. Kolen, The partial constraint satisfaction problem: Facets and lifting theorems, Operations Research Letters, vol.23, pp.3-589, 1998.

M. P. Kumar and P. H. Torr, Efficiently solving convex relaxations for MAP estimation, ICML, 2008.
DOI : 10.1145/1390156.1390242

M. P. Kumar, P. H. Torr, and A. Zisserman, Solving Markov random fields using second order cone programming relaxations, CVPR, volume I, pp.1045-1052, 2006.
DOI : 10.1109/cvpr.2006.283

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

J. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal of Optimization, vol.11, pp.796-817, 2001.

M. Muramatsu and T. Suzuki, A new second-order cone programming relaxation for max-cut problems, Journal of Operations Research of Japan, vol.43, pp.164-177, 2003.

C. Olsson, A. P. Eriksson, and F. Kahl, Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming, CVPR, pp.1-8, 2007.
DOI : 10.1109/cvpr.2007.383202
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.124.2774

P. Ravikumar and J. Lafferty, Quadratic programming relaxations for metric labelling and Markov random field MAP estimation, ICML, 2006.

P. Ravikumar, A. Agarwal, and M. Wainwright, Message-passing for graph-structured linear programs: Proximal projections, convergence and rounding schemes, ICML, 2008.

C. Schellewald and C. Schnorr, Subgraph matching with semidefinite programming, IWCIA, 2003.

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

M. Schlesinger, Sintaksicheskiy analiz dvumernykh zritelnikh singnalov v usloviyakh pomekh (syntactic analysis of two-dimensional visual signals in noisy conditions), Kibernetika, vol.4, pp.113-130, 1976.

M. Schlesinger and B. Flach, Some solvable subclass of structural recognition problems, Czech Pattern Recognition Workshop, 2000.

M. Schlesinger and V. Giginyak, Solution to structural recognition (MAX,+)-problems by their equivalent transformations. Part 1, Control Systems and Computers, vol.1, pp.3-15, 2007.

M. Schlesinger and V. Giginyak, Solution to structural recognition (MAX,+)-problems by their equivalent transformations, Control Systems and Computers, vol.2, pp.3-18, 2007.

R. Szeliski, R. Zabih, D. Scharstein, O. Veksler, V. Kolmogorov et al., A comparative study of energy minimization methods for markov random fields, ECCV, pages II, pp.16-29, 2006.

P. H. Torr, Solving Markov random fields using semidefinite programming, AISTATS, 2003.

M. Wainwright and M. Jordan, Graphical models, exponential families, and variational inference, 2003.
DOI : 10.1561/2200000001
URL : http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.192.2462

M. Wainwright and M. Jordan, Treewidth-based conditions for exactness of the Sherali-Adams and Lasserre relaxations, 2004.

M. Wainwright, T. Jaakola, and A. Willsky, MAP estimation via agreement on trees: Message passing and linear programming, IEEE Trans. on Information Theory, issue.11, pp.513697-3717, 2005.

T. Werner, A linear programming approach to max-sum problem: A review, 2007.

J. Yedidia, W. Freeman, and Y. Weiss, Understanding belief propagation and its generalizations, 2001.