IS = { zkontrolovano 30 Nov 2007 },
  UPDATE  = { 2007-07-24 },
  author =       {Werner, Tom{\'a}{\v s}},
  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},
  publisher =    {IEEE Computer Society},
  address =      {Los Alamitos, USA},
  issn =         {0162-8828},
  keywords = {Markov random fields, undirected graphical models,
    constraint satisfaction, belief propagation,
    linear programming relaxation, max-sum, max-plus, max-product, 
    supermodular optimization},
  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.},
  project =      {IST-004176 COSPAL},
  psurl = {
[article pdf],
[slides pdf],
[www page with software and links to cited papers]
  authorship =   {100},