2013
CVPR
CVPR 2013
Universality of the Local Marginal Polytope
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.
🚀
Conference Pioneer
- CVPR 2013
🌉
Interdisciplinary Bridge
- Artificial Intelligence and Mathematics & Optimization
🐣
Hot Topic Early Bird
- linear programming