A Linear Programming Approach to Max-Sum Problem: A Review
Author:
- 21 May 2007
- journal article
- review article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Pattern Analysis and Machine Intelligence
- Vol. 29 (7) , 1165-1179
Abstract
The max-sum labeling problem, defined as maximizing a sum of binary (i.e., pairwise) functions of discrete variables, is a general NP-hard optimization problem with many applications, such as computing the MAP configuration of a Markov random field. We review a not widely known approach to the problem, developed by Ukrainian researchers Schlesinger et al. in 1976, and show how it contributes to recent results, most importantly, those on the convex combination of trees and tree-reweighted max-product. In particular, we review Schlesinger et al.'s upper bound on the max-sum criterion, its minimization by equivalent transformations, its relation to the constraint satisfaction problem, the fact that this minimization is dual to a linear programming relaxation of the original problem, and the three kinds of consistency necessary for optimality of the upper bound. We revisit problems with Boolean variables and supermodular problems. We describe two algorithms for decreasing the upper bound. We present an example application for structural image analysis.Keywords
This publication has 48 references indexed in Scilit:
- Supermodular functions and the complexity of MAX CSPDiscrete Applied Mathematics, 2005
- A New Class of Upper Bounds on the Log Partition FunctionIEEE Transactions on Information Theory, 2005
- What energy functions can be minimized via graph cuts?IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004
- Exact optimization for markov random fields with convex priorsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2003
- Tree-based reparameterization framework for analysis of sum-product and related algorithmsIEEE Transactions on Information Theory, 2003
- Pseudo-Boolean optimizationDiscrete Applied Mathematics, 2002
- Fast approximate energy minimization via graph cutsIEEE Transactions on Pattern Analysis and Machine Intelligence, 2001
- The partial constraint satisfaction problem: Facets and lifting theoremsOperations Research Letters, 1998
- Methods and applications of (max,+) linear algebra1997
- Perspectives of Monge properties in optimizationDiscrete Applied Mathematics, 1996