A Linear Programming Approach to Max-Sum Problem: A Review

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 probl...

Full description

Saved in:
Bibliographic Details
Published in:IEEE transactions on pattern analysis and machine intelligence 2007-07, Vol.29 (7), p.1165-1179
Main Author: Werner, T.
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Artificial Intelligence
belief propagation
Computer science
control theory
systems
Computer Society
constraint satisfaction
Exact sciences and technology
Game Theory
Image analysis
Image Enhancement - methods
Image Interpretation, Computer-Assisted - methods
Imaging, Three-Dimensional - methods
Intelligence
Labeling
Linear programming
linear programming relaxation
Markov random fields
Mathematical analysis
Mathematical models
max-plus
max-product
max-sum
Minimization
Noise generators
Optimization
Pattern recognition
Pattern Recognition, Automated - methods
Pattern recognition. Digital image processing. Computational geometry
Programming, Linear
Studies
supermodular optimization
Testing
undirected graphical models
Upper bound
Upper bounds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0162-8828
1939-3539
DOI:10.1109/TPAMI.2007.1036