IS      = { zkontrolovano 19 Oct 2010 },
  UPDATE  = { 2010-02-01 },
  author =       {Werner, Tom{\'a}{\v s}},
  title =        {Revisiting the Linear Programming Relaxation Approach to
    Gibbs Energy Minimization and Weighted Constraint Satisfaction},
  journal =      {IEEE Trans. Pattern Analysis and Machine Intelligence},
  year =         {2010},
  volume =       {32},
  number =       {8},
  pages =        {1474--1488},
  month =        {August},
  publisher =    {IEEE Computer Society},
  address =      {Los Alamitos, USA},
  issn =         {0162-8828},
  keywords = { weighted constraint satisfaction, Gibbs distribution,
    graphical  model, Markov random field, linear programming relaxation, 
    marginal polytope, cut polytope, cutting plane algorithm, 
    global constraint, supermodularity, tree-reweighted max-product},
  annote = { We present a number of contributions to the LP relaxation
    approach to weighted constraint satisfaction (= Gibbs energy
    minimization).  We link this approach to many works from
    constraint programming, which relation has so far been ignored in
    machine vision and learning.  While the approach has been mostly
    considered only for binary constraints, we generalize it to n-ary
    constraints in a simple and natural way. This includes a simple
    algorithm to minimize the LP-based upper bound, n-ary max-sum
    diffusion -- however, we consider using other bound-optimizing
    algorithms as well.  The diffusion iteration is tractable for a
    certain class of high-arity constraints represented as a
    black-box, which is analogical to propagators for global
    constraints CSP.  Diffusion exactly solves permuted n-ary
    supermodular problems.  A hierarchy of gradually tighter LP
    relaxations is obtained simply by adding various zero constraints
    and coupling them in various ways to existing constraints. Zero
    constraints can be added incrementally, which leads to a cutting
    plane algorithm. The separation problem is formulated as finding
    an unsatisfiable subproblem of a CSP.},
  authorship = {100},
  project =    {ICT-215078 DIPLECS only EU, MSM6840770038},