@InBook{Zivny-Werner-Prusa-ASP-MIT2014,
  IS = { zkontrolovano 08 Jan 2015 },
  UPDATE  = { 2014-12-16 },
  author =      {{\v Z}ivn{\' y}, Stanislav and Werner, Tom{\' a}{\v
                  s} and Pr{\r u}{\v s}a, D aniel},
  affiliation = {NULL-13133-13133},
  title =       {The Power of LP Relaxation for MAP Inference},
  book_title =  {Advanced Structured Prediction},
  year =        {2014},
  month =       {December},
  pages = {19-42},
 authorship = {40-30-30},
editor =      {Nowozin, Sebastian and Gehler, Peter V. and Jancsary,
                  Jeremy and Lampert, Christoph H.},
  publisher =   {The MIT Press},
  address =     {Cambridge, USA},
  isbn =        {978-0-262-02837-0},
  book_pages =  {456},
  annote =      {Minimization of a partially separable function of
                  many discrete variables is ubiquitous in machine
                  learning and computer vision, in tasks like maximum
                  a posteriori (MAP) inference in graphical models, or
                  structured prediction.  Among successful approaches
                  to this problem is linear programming (LP)
                  relaxation. We discuss this LP relaxation from two
                  aspects.  First, we review recent results which
                  characterize languages (classes of functions
                  permitted to form the objective function) for which
                  the problem is solved by the relaxation exactly.
                  Second, we show that solving the LP relaxation is
                  not easier than solving any linear program, which
                  makes a discovery of an efficient algorithm for the
                  LP relaxation unlikely.},
  keywords =    {graphical model, Markov random field, discrete energy minimization,
        valued constraint satisfaction, linear programming relaxation},
  project =     {GACR P202/12/2071, FP7-ICT-247525 HUMAVIPS, FP7-ICT-270138 DARWIN},
  psurl       = {[ZivWerPru-LP-MIT2014.pdf]},
}