cvpr cvpr2013 cvpr2013-448 cvpr2013-448-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: unkown-author
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.
[1] E. Boros and P. L. Hammer. Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1-3): 155–225, 2002. 6
[2] C. Chekuri, S. Khanna, J. Naor, and L. Zosin. Approximation algorithms for the metric labeling problem via a new linear programming formulation. In Symposium on Discrete Algorithms, pages 109–1 18, 2001. 1
[3] D. Cohen, M. Cooper, P. Jeavons, and A. Krokhin. The complexity of soft constraint satisfaction. Artificial Intelligence, 170:983–1016, 2006. 1
[4] J. A. De Loera and S. Onn. All linear and integer programs are slim 3-way transportation programs. SIAM J. on Optimization, 17(3):806–821, 2006. 1
[5] N. Karmarkar. A new polynomial-time algorithm for linear programming. In Proceedings of the sixteenth annual ACM symposium on Theory of computing, STOC ’84, pages 302– 311, New York, NY, USA, 1984. ACM. 6
[6] V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Trans. Pattern Analysis and Machine Intelligence, 28(10): 1568–1583, 2006. 6
[7] A. Koster, C. van Hoesel, and A. Kolen. The partial constraint satisfaction problem: Facets and lifting theorems. Operations Research Letters, 23(3–5):89–97, 1998. 1
[8] C. Rother, V. Kolmogorov, V. S. Lempitsky, and M. Szummer. Optimizing binary MRFs via extended roof duality. In Conf. Computer Vision and Pattern Recognition (CVPR), 2007. 6
[9] M. I. Shlezinger. Syntactic analysis of two-dimensional visual signals in noisy conditions. Cybernetics and Systems Analysis, 12(4):612–628, 1976. Translation from Russian. 1
[10] M. J. Wainwright and M. I. Jordan. Graphical models, exponential families, and variational inference. Foundations and Trends in Machine Learning, 1(1-2): 1–305, 2008. 1
[11] T. Werner. A linear programming approach to max-sum problem: A review. IEEE Trans. Pattern Analysis and Machine Intelligence, 29(7):1 165–1 179, 2007. 2, 6 111777444311