Title :
Universality of the Local Marginal Polytope
Author :
Prusa, Daniel ; Werner, T.
Author_Institution :
Center for Machine Perception, Czech Tech. Univ., Prague, Czech Republic
Abstract :
We show that solving the LP relaxation of the MAP inference problem in graphical models (also known as the min-sum problem, energy minimization, or weighted constraint satisfaction) is not easier than solving any LP. More precisely, any polytope is linear-time represent able 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.
Keywords :
computational geometry; linear programming; minimisation; LP relaxation; MAP inference problem; energy minimization; graphical models; infinite weights; linear optimization; linear time representation; local marginal polytope; min sum problem; weighted constraint satisfaction; Complexity theory; Encoding; Equations; Face; Graphical models; Optimization; Vectors;
Conference_Titel :
Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on
Conference_Location :
Portland, OR
DOI :
10.1109/CVPR.2013.227
