IS = { zkontrolovano 16 Jan 2009 },
  UPDATE  = { 2008-08-28 },
  author =       {Werner, Tom{\'a}{\v s}},
  title =        {High-arity Interactions, Polyhedral Relaxations, 
                  and Cutting Plane Algorithm for Soft Constraint 
                  Optimisation ({MAP-MRF})},
  year =         {2008},
  pages =        {109--116},
  booktitle =    {CVPR 2008: Proceedings of the 2008 IEEE Computer Society
    Conference on Computer Vision and Pattern Recognition},
  publisher =   {Omnipress},
  address =     {Madison, USA},
  isbn =        {978-1-4244-2243-2},
  issn =        {1063-6919},
  book_pages =  {2954},
  month =        {June},
  day =          {24-26},
  venue =        {Anchorage, USA},
  organization = {IEEE Computer Society},
  annote = {LP relaxation approach to soft constraint optimisation
    (i.e. MAP-MRF) has been mostly considered only for binary
    problems.  We present its generalisation to n-ary problems,
    including a simple algorithm to optimise the LP bound, n-ary
    max-sum diffusion. As applications, we show that a hierarchy of
    gradually tighter polyhedral relaxations of MAP-MRF is obtained by
    adding zero interactions. We propose a cutting plane algorithm,
    where cuts correspond to adding zero interactions and the
    separation problem to finding an unsatisfiable constraint
    satisfaction subproblem.  Next, we show that certain high-arity
    interactions, e.g. certain global constraints, can be included
    into the framework in a principled way.  Finally, we prove that
    n-ary max-sum diffusion finds global optimum for n-ary
    supermodular problems.},
  keywords =    {soft constraint satisfaction, Markov random fields, 
                 MRF, Gibbs energy minimization, linear programming relaxation, 
                 supermodular constraints, global soft constraints},
  authorship =  {100},
  project =     {ICT-215078 DIPLECS, MSM6840770038},
  prestige    = {important},
  note        = {CD-ROM},
  psurl       = {[[paper pdf],
[errata pdf],
[slides pdf]]},