@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]}, }