DocumentCode
3331859
Title
Universality of the Local Marginal Polytope
Author
Prusa, Daniel ; Werner, T.
Author_Institution
Center for Machine Perception, Czech Tech. Univ., Prague, Czech Republic
fYear
2013
fDate
23-28 June 2013
Firstpage
1738
Lastpage
1743
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Computer Vision and Pattern Recognition (CVPR), 2013 IEEE Conference on
Conference_Location
Portland, OR
ISSN
1063-6919
Type
conf
DOI
10.1109/CVPR.2013.227
Filename
6619071
Link To Document