Universality of the Local Marginal Polytope

CVPR 2013

doi:10.1109/CVPR.2013.227 /cvpr/2013/prusa2013cvpr-universality/

Abstract

We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the minsum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time representable by a local marginal polytope and any LP can be reduced in linear time to a linear optimization (allowing infinite weights) over a local marginal polytope.

PDF CVPR Semantic Scholar

Cite

Text

Prusa and Werner. "Universality of the Local Marginal Polytope." Conference on Computer Vision and Pattern Recognition, 2013. doi:10.1109/CVPR.2013.227

Markdown

[Prusa and Werner. "Universality of the Local Marginal Polytope." Conference on Computer Vision and Pattern Recognition, 2013.](https://mlanthology.org/cvpr/2013/prusa2013cvpr-universality/) doi:10.1109/CVPR.2013.227

BibTeX

@inproceedings{prusa2013cvpr-universality,
  title     = {{Universality of the Local Marginal Polytope}},
  author    = {Prusa, Daniel and Werner, Tomas},
  booktitle = {Conference on Computer Vision and Pattern Recognition},
  year      = {2013},
  doi       = {10.1109/CVPR.2013.227},
  url       = {https://mlanthology.org/cvpr/2013/prusa2013cvpr-universality/}
}