IS = { zkontrolovano 30 Dec 2005 },
  UPDATE  = { 2005-10-03 },
  author =       {Werner, Tom{\'a}{\v s}},
  title =        {A Linear Programming Approach to Max-sum Problem: {A} review},
  institution =  {Center for Machine Perception, K13133 FEE Czech Technical
  address =      {Prague, Czech Republic},
  year =         {2005},
  month =        {December},
  type =         {Research Report},
  number =       {{CTU--CMP--2005--25}},
  issn =         {1213-2365},
  pages =        {40},
  figures =      {23},
  authorship =   {100},
  psurl =        {[Werner-TR-2005-25.pdf]},
  project =      { COSPAL IST-004176},
  annote = {The max-sum (labeling) problem of the second order is
    defined as maximizing a sum of bivariate functions of discrete
    variables. It is a general optimization problem with numerous
    applications, e.g., computing a MAP configuration of a Markov
    random field on an arbitrary graph. Recently, it has received much
    attention in context of inference in graphical models, resulting
    in approaches based on linear programming and belief
    propagation. It is unknown that a similar approach, based on
    linear programming relaxation, was developed already in 1970's by
    Schlesinger \etal. This report surveys this unnoticed work in a
    unified framework, including published and several unpublished
    results. Compared to the known works, this old theory is simpler,
    easier to grasp, and brings several new insights and results. The
    Lagrangian dual of an integer linear programming formulation is
    solved first, which can be interpreted as minimizing the quantity
    called energy by equivalent transformations of the problem. The
    solution set of the original problem is obtained from the dual
    optimum by solving a consistent labeling problem. If this
    consistent labeling problem has no solution, the max-sum problem
    cannot be solved by the approach, in other words, the LP
    relaxation is not tight. We analyse the LP pair in detail and give
    an iterative and a combinatorial algorithm which sometimes solves
    the dual. We present examples of experiments with syntactic
    analysis of images.},
  keywords =     {pattern recognition, max-sum, max-prod, sum-prod, min-sum,
                  consistent labeling, Markov random field, 
                  Gibbs distribution, constraint satisfaction, 
                  arc consistency, belief propagation, tree agreement},