Universality of the Local Marginal Polytope

Daniel Prusa, Tomas Werner; The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2013, pp. 1738-1743

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.

Related Material


[pdf]
[bibtex]
@InProceedings{Prusa_2013_CVPR,
author = {Prusa, Daniel and Werner, Tomas},
title = {Universality of the Local Marginal Polytope},
booktitle = {The IEEE Conference on Computer Vision and Pattern Recognition (CVPR)},
month = {June},
year = {2013}
}