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

Werner, Tomáš
IEEE Trans. Pattern Analysis and Machine Intelligence
Volume 29, Number 7, Pages 1165-1179
July, 2007

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.

Bibtex entry

@Article{Werner-PAMI07,
  author =       {Werner, Tom{\'a}{\vs}},
  title =        {A Linear Programming Approach to Max-sum Problem: {A} Review},
  journal =      {IEEE Trans. Pattern Analysis and Machine Intelligence},
  year =         {2007},
  volume =    {29},
  number =    {7},
  pages =     {1165--1179},
  month =     {July},
  annote = {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.},
}