D. Batra, A. C. Gallagher, D. Parikh, and T. Chen, Beyond trees: Mrf inference via outer-planar decomposition, IEEE Conference on Computer Vision and Pattern Recognition (CVPR, vol.21, p.22, 2010.

D. Batra, S. Nowozin, and P. Kohli, Tighter relaxations for map-mrf inference: A local primal-dual gap based separation algorithm, 'International Conference on Artificial Intelligence and Statistics, p.13, 2011.

D. Batra, P. Yadollahpour, A. Guzman-rivera, and G. Shakhnarovich, Diverse m-best solutions in markov random fields, p.22, 2012.

M. Bergtholdt, J. Kappes, S. Schmidt, and C. Schnörr, A study of parts-based object class detection using complete graphs, International Journal of Computer Vision (IJCV), vol.87, issue.1-2, 2010.

A. Blake, P. Kohli, and C. Rother, Markov random fields for vision and image processing, p.32, 2011.

N. Boumal, V. Voroninski, and A. Bandeira, The non-convex burer-monteiro approach works on smooth semidefinite programs, Advances in Neural Information Processing Systems (NIPS), p.26, 2016.

N. Boumal, V. Voroninski, and A. S. Bandeira, Deterministic guarantees for burermonteiro factorizations of smooth semidefinite programs, 2018.

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, Distributed optimization and statistical learning via the alternating direction method of multipliers, Foundations and Trends® in Machine learning, vol.3, issue.1, pp.1-122, 2011.

S. Boyd and L. Vandenberghe, Convex optimization, p.25, 2004.

M. Braverman, K. Makarychev, Y. Makarychev, and A. Naor, The grothendieck constant is strictly smaller than krivine's bound, Forum of Mathematics, Pi', vol.1, p.34, 2013.

S. Burer and R. D. Monteiro, A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization, Mathematical Programming, vol.95, issue.2, pp.329-357, 2003.

S. Burer and R. D. Monteiro, Local minima and convergence in low-rank semidefinite programming, Mathematical Programming, vol.103, issue.3, pp.427-444, 2005.

V. Chandrasekaran, N. Srebro, and P. Harsha, Complexity of inference in graphical models, Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI, p.35, 2008.

M. Charikar, K. Makarychev, and Y. Makarychev, Near-optimal algorithms for maximum constraint satisfaction problems, ACM Transactions on Algorithms (TALG), vol.5, issue.3, p.33, 2009.

B. Chazelle, C. Kingsford, and M. Singh, A semidefinite programming approach to side chain positioning with new rounding strategies, INFORMS Journal on Computing, vol.16, issue.4, pp.380-392, 2004.

E. Chlamtac and M. Tulsiani, Convex relaxations and integrality gaps, in 'Handbook on semidefinite, vol.36, pp.139-169, 2012.

M. C. Cooper, S. De-givry, M. Sánchez, T. Schiex, M. Zytnicki et al., Soft arc consistency revisited, Artificial Intelligence, vol.174, issue.7-8, pp.449-478, 2010.

T. Cour and J. Shi, Solving markov random fields with spectral relaxation, 'International Conference on Artificial Intelligence and Statistics, p.34, 2007.

M. M. Deza and M. Laurent, Geometry of cuts and metrics, vol.15, p.33, 2009.

J. C. Duchi, D. Tarlow, G. Elidan, and D. Koller, Using combinatorial optimization within max-product belief propagation, Advances in Neural Information Processing Systems (NIPS), p.21, 2007.

M. A. Erdogdu, Y. Deshpande, and A. Montanari, Inference in graphical models via semidefinite programming hierarchies, Advances in Neural Information Processing Systems (NIPS)'. 28, vol.29, p.36, 2017.

P. F. Felzenszwalb and J. J. Mcauley, Fast inference with min-sum matrix product, IEEE Transactions on Pattern Analysis and Machine Intelligence, vol.19, issue.12, pp.2549-2554, 2011.

R. Frostig, S. Wang, P. S. Liang, and C. D. Manning, Simple map inference via low-rank relaxations, Advances in Neural Information Processing Systems (NIPS), p.30, 2014.

A. Globerson and T. S. Jaakkola, Fixing max-product: Convergent message passing algorithms for map lp-relaxations, in 'Advances in neural information processing systems (NIPS, p.11, 2008.

M. X. Goemans and D. P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, Journal of the ACM (JACM), vol.42, issue.6, p.33, 1995.

G. H. Golub and C. F. Van-loan, Matrix computations, p.28, 2013.

T. Hazan and A. Shashua, Convergent message-passing algorithms for inference over general graphs with convex free energies, Twenty-Fourth Conference on Uncertainty in Artificial Intelligence (UAI, p.26, 2008.

Q. Huang, Y. Chen, and L. Guibas, Scalable semidefinite relaxation for maximum a posterior estimation, 'International Conference on Machine Learning (ICML), vol.27, p.34, 2014.

, Semidefinite programming and graph algorithms, 2014.

J. K. Johnson, Convex relaxation methods for graphical models: Lagrangian and maximum entropy approaches, vol.17, p.18, 2008.

J. H. Kappes, B. Andres, F. A. Hamprecht, C. Schnörr, S. Nowozin et al., A comparative study of modern inference techniques for structured discrete energy minimization problems, International Journal of Computer Vision, vol.115, issue.2, p.21, 2015.
URL : https://hal.archives-ouvertes.fr/hal-01247122

J. H. Kappes, S. Schmidt, and C. Schnörr, Mrf inference by k-fan decomposition and tight lagrangian relaxation, p.22, 2010.

P. Kohli, A. Shekhovtsov, C. Rother, V. Kolmogorov, and P. Torr, On partial optimality in multi-label mrfs, 'International Conference on Machine Learning (ICML, 2008.

A. Kolla, Merging Techniques for Combinatorial Optimization: Spectral Graph Theory and Semidefinite Programming, p.34, 2009.

D. Koller and N. Friedman, Probabilistic graphical models: principles and techniques, vol.1, p.9, 2009.

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.

N. Komodakis, M. P. Kumar, and N. Paragios, '(hyper)-graphs inference through convex relaxations and move making algorithms: Contributions and applications in artificial vision, Foundations and Trends® in Computer Graphics and Vision, vol.10, issue.1, pp.1-102, 2016.

N. Komodakis and N. Paragios, Beyond loose lp-relaxations: Optimizing mrfs by repairing cycles, vol.5, p.17, 2008.
URL : https://hal.archives-ouvertes.fr/hal-00918715

N. Komodakis and N. Paragios, Beyond pairwise energies: Efficient optimization for higher-order mrfs, IEEE Conference on Computer Vision and Pattern Recognition (CVPR, vol.21, p.23, 2009.

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, p.26, 2011.
URL : https://hal.archives-ouvertes.fr/hal-00856311

I. Kovtun, Partial optimal labeling search for a np-hard subclass of (max,+) problems, in 'Joint Pattern Recognition Symposium, vol.32, pp.402-409, 2003.

M. P. Kumar, V. Kolmogorov, and P. H. Torr, An analysis of convex relaxations for map estimation of discrete mrfs, Journal of Machine Learning Research, vol.10, p.23, 2009.
URL : https://hal.archives-ouvertes.fr/hal-00773608

J. B. Lasserre, Global optimization with polynomials and the problem of moments, SIAM Journal on optimization, vol.11, issue.3, p.28, 2001.

M. Laurent, A comparison of the sherali-adams, lovász-schrijver, and lasserre relaxations for 0-1 programming, Mathematics of Operations Research, vol.28, issue.3, pp.470-496, 2003.

M. Li, A. Shekhovtsov, and D. Huber, Complexity of discrete energy minimization problems, European Conference on Computer Vision (ECCV, 2016.

Y. Li and R. Zemel, High order regularization for semi-supervised learning of structured output problems, 'International Conference on Machine Learning (ICML), p.22, 2014.

J. Malick, The spherical constraint in boolean quadratic programs, Journal of Global Optimization, vol.39, issue.4, 2007.
URL : https://hal.archives-ouvertes.fr/inria-00070518

J. J. Mcauley and T. S. Caetano, Faster algorithms for max-product message-passing, Journal of Machine Learning Research, vol.12, pp.1349-1388, 2011.

S. Mei, T. Misiakiewicz, A. Montanari, and R. I. Oliveira, Solving sdps for synchronization and maxcut problems via the grothendieck inequality, Conference on Learning Theory, vol.26, p.30, 2017.

O. Meshi, T. Jaakkola, and A. Globerson, Smoothed coordinate descent for map inference, vol.11, p.12, 2014.

O. Meshi, B. London, A. Weller, and D. Sontag, Train and test tightness of lp relaxations in structured prediction, Journal of Machine Learning Research, vol.20, issue.13, pp.1-34, 2019.

E. Mezuman, D. Tarlow, A. Globerson, and Y. Weiss, Tighter linear program relaxations for high order graphical models, Uncertainty in Artificial Intelligence, p.23, 2013.

E. Mezuman and Y. Weiss, Globally optimizing graph partitioning problems using message passing, 'International Conference on Artificial Intelligence and Statistics, p.22, 2012.

N. Noorshams and M. J. Wainwright, Stochastic belief propagation: A low-complexity alternative to the sum-product algorithm, IEEE Transactions on Information Theory, vol.59, issue.4, 1981.

C. Olsson, A. P. Eriksson, and F. Kahl, Solving large scale binary quadratic problems: Spectral methods vs. semidefinite programming, IEEE Conference on Computer Vision and Pattern Recognition (CVPR, p.34, 2007.

L. Otten and R. Dechter, Anytime and/or depth-first search for combinatorial optimization, AI Communications, vol.25, issue.3, pp.211-227, 2012.

P. A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Mathematical programming, vol.96, issue.2, p.28, 2003.

G. Pataki, On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues, Mathematics of operations research, vol.23, issue.2, pp.339-358, 1998.

J. Peng, T. Hazan, N. Srebro, and J. Xu, Approximate inference by intersecting semidefinite bound and local polytope, 'International Conference on Artificial Intelligence and Statistics (AISTATS)'. 26, vol.27, p.34, 2012.

, Probabilistic inference challenge, 2011.

B. Potetz and T. S. Lee, Efficient belief propagation for higher-order cliques using linear constraint nodes, Computer Vision and Image Understanding, vol.112, issue.1, pp.39-54, 2008.

P. Raghavendra, Generic techniques to round sdp relaxations, 'International Symposium on Mathematical Foundations of Computer Science, vol.33, pp.34-34, 2011.

P. Ravikumar, A. Agarwal, and M. J. Wainwright, Message-passing for graphstructured linear programs: Proximal methods and rounding schemes, Journal of Machine Learning Research, vol.11, p.33, 2010.

P. Ravikumar and J. Lafferty, Quadratic programming relaxations for metric labeling and markov random field map estimation, 'International Conference on Machine learning (ICML, p.24, 2006.

C. Rother, P. Kohli, W. Feng, and J. Jia, Minimizing sparse higher order energy functions of discrete variables, IEEE Conference on Computer Vision and Pattern Recognition (CVPR)'. 18, vol.21, p.23, 2009.

M. Rowland, A. Pacchiano, and A. Weller, Conditions beyond treewidth for tightness of higher-order lp relaxations, in 'International Conference on Artificial Intelligence and Statistics (AISTATS)'. 5, vol.35, p.36, 2017.

B. Savchynskyy and S. Schmidt, Getting feasible variable estimates from infeasible ones: Mrf local polytope study, vol.12, pp.133-158, 2014.

N. N. Schraudolph and D. Kamenetsky, Efficient exact inference in planar ising models, Advances in Neural Information Processing Systems (NIPS, vol.20, p.22, 2009.

A. Schrijver, Combinatorial optimization: polyhedra and efficiency, vol.24, p.32, 2003.

S. E. Shimony, Finding maps for belief networks is np-hard, Artificial Intelligence, vol.68, issue.2, pp.399-410, 1994.

. Simons-institute, Spectral graph theory and optimization symposium, 2017.

D. Sontag, D. K. Choe, and Y. Li, Efficiently searching for frustrated cycles in map inference, Uncertainty in Artificial Intelligence, vol.17, p.21, 2012.

D. Sontag, A. Globerson, and T. Jaakkola, Introduction to dual decomposition for inference, Optimization for Machine Learning, vol.1, issue.8, pp.219-254, 2011.

D. Sontag, A. Globerson, and T. S. Jaakkola, Clusters and coarse partitions in lp relaxations, in 'Advances in Neural Information Processing Systems (NIPS), p.14, 2009.

D. Sontag and T. S. Jaakkola, New outer bounds on the marginal polytope, in 'Advances in Neural Information Processing Systems (NIPS)'. 5, 6, 7, 10, vol.17, p.32, 2007.

D. Sontag, T. Meltzer, A. Globerson, T. Jaakkola, and Y. Weiss, Tightening lp relaxations for map using message passing, Uncertainty in Artificial Intelligence (UAI)'. 5, vol.10, p.34, 2008.

M. Sun, M. Telaprolu, H. Lee, and S. Savarese, Efficient and exact map-mrf inference using branch and bound, 'International Conference on Artificial Intelligence and Statistics, p.32, 2012.

P. Swoboda, A. Shekhovtsov, J. H. Kappes, C. Schnorr, and B. Savchynskyy, Partial optimality by pruning for map-inference with general graphical models, IEEE transactions on pattern analysis and machine intelligence (PAMI), vol.32, pp.1370-1382, 2016.

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, PAMI), vol.30, issue.6, pp.1068-1080, 2008.

D. Tarlow, I. Givoni, and R. Zemel, hop-map: Efficient message passing with high order potentials, 'International Conference on Artificial Intelligence and Statistics, vol.21, p.23, 2010.

J. Thapper and S. ?ivn?, The complexity of finite-valued csps', Journal of the ACM (JACM), vol.63, issue.4, p.35, 2016.
URL : https://hal.archives-ouvertes.fr/hal-01796719

M. J. Wainwright, T. S. Jaakkola, and A. S. Willsky, Map estimation via agreement on trees: message-passing and linear programming, IEEE Transactions on Information Theory, vol.51, issue.11, p.10, 2005.

M. J. Wainwright and M. I. Jordan, Semidefinite relaxations for approximate inference on graphs with cycles, Advances in Neural Information Processing Systems (NIPS)'. 25, vol.27, p.28, 2004.

M. J. Wainwright and M. I. Jordan, Treewidth-based conditions for exactness of the sherali-adams and lasserre relaxations, vol.35, p.36, 2004.

M. J. Wainwright and M. I. Jordan, Graphical models, exponential families, and variational inference, Foundations and Trends® in Machine Learning, vol.1, issue.1-2, p.26, 2008.

H. Wang and D. Koller, A fast and exact energy minimization algorithm for cycle mrfs, 'International Conference on Machine Learning (ICML), vol.19, p.20, 2013.

P. Wang, C. Shen, . Van-den, and A. Hengel, A fast semidefinite approach to solving binary quadratic problems, p.30, 2013.

P. Wang, C. Shen, and A. Van-den-hengel, Efficient sdp inference for fully-connected crfs based on low-rank decomposition, IEEE Conference on Computer Vision and Pattern Recognition (CVPR, vol.30, p.34, 2015.

P. Wang, C. Shen, A. Van-den-hengel, and P. H. Torr, Efficient semidefinite branch-and-cut for map-mrf inference, International Journal of Computer Vision (IJCV), vol.117, issue.3, p.34, 2016.

A. Weller, M. Rowland, and D. Sontag, Tightness of lp relaxations for almost balanced models, 'International Conference on Artificial Intelligence and Statistics, vol.5, p.35, 2016.

Z. Wen, D. Goldfarb, and W. Yin, Alternating direction augmented lagrangian methods for semidefinite programming, Mathematical Programming Computation, vol.2, issue.3-4, pp.203-230, 2010.

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.

T. Werner, High-arity interactions, polyhedral relaxations, and cutting plane algorithm for soft constraint optimisation (map-mrf), in 'IEEE Conference on Computer Vision and Pattern Recognition (CVPR)'. 5, vol.10, p.14, 2008.

T. Werner, Revisiting the linear programming relaxation approach to gibbs energy minimization and weighted constraint satisfaction, IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI), vol.32, issue.8, pp.1474-1488, 2010.

C. Yanover, T. Meltzer, and Y. Weiss, Linear programming relaxations and belief propagation-an empirical study, Journal of Machine Learning Research, vol.7, p.14, 2006.

J. Yarkony, R. Morshed, A. T. Ihler, and C. C. Fowlkes, Tightening mrf relaxations with planar subproblems, Uncertainty in Artificial Intelligence, vol.19, p.21, 2011.

J. S. Yedidia, W. T. Freeman, and Y. Weiss, Constructing free-energy approximations and generalized belief propagation algorithms, IEEE Transactions on information theory, vol.51, issue.7, pp.2282-2312, 2005.

Y. Zheng, P. Chen, and J. Cao, Map-mrf inference based on extended junction tree representation, IEEE Conference on Computer Vision and Pattern Recognition (CVPR, p.22, 2012.