@TechReport{mqpbo-08-TR,
  IS = { zkontrolovano 18 Jan 2009 },
  UPDATE  = { 2008-11-27 },
  author = {Shekhovtsov, A. and Kolmogorov, V. and Kohli, P. and Hlavac, V. and 
            Rother, C. and Torr, P.},
  title = {{LP}-relaxation of binarized energy minimization},
  year = {2008},
  month = {June},
  institution = {Center for Machine Perception, 
                 K13133 FEE Czech Technical University},
  address = {Prague, Czech Republic},
  type = {Research Report},
  pages = {26},
  number = {CTU--CMP--2007--27},
  issn = {1213-2365},
  annote = {We address the problem of energy minimization, which is
    (1) generally NP-complete and (2) involves many discrete variables
    - commonly a 2D array of them, arising from an MRF model.  One of
    the approaches to the problem is to formulate it as integer linear
    programming and relax integrality constraints. However this can be
    done in a number of possible ways. One, widely applied previously
    (LP-1) [19, 13, 4, 22, 9, 23], appears to lead to a large-scale
    linear program which is not practical to solve with general LP
    methods.  A number of algorithms were developed which attempt to
    solve the problem exploiting its structure [14, 23, 22, 9],
    however their common drawback is that they may converge to a
    suboptimal point.  The other LP relaxation we consider here is
    constructed by (1) refor- mulating the optimization problem in the
    form of a function of binary vari- ables [18], and (2) applying
    the roof duality relaxation [6] to the reformulated problem. We
    refer to the resulting relaxation as LP-2. It is different from
    LP-1 in many respects, and this is the main question of our
    study. Most importantly, it is possible to apply an ef?cient,
    fully combinatorial, algorithm to solve the relaxed problem.  We
    also derive the following relations: a) LP-1 is generally a
    tighter re- laxation than LP-2, b) LP-2 provides constraints on
    optimal integer con?g- urations, which allows one to identify "a
    part" of an optimal solution, c) a subclass of problems can be
    identi?ed for which LP-2 is as tight as LP-1 pro- viding
    additional characterization of solutions of LP-1 for this
    subclass.  Our last contribution is providing an alternative
    formulation of LP-2: we prove that it is equivalent to computing a
    decomposition of the energy into submodular and supermodular parts
    so that the sum of the lower bounds for each part is maximized.},
  project = {ICT-215078 DIPLECS, MSM6840770038},
keywords    = { MRF, energy minimization, pseudo-Boolean optimization, persistency, partial optimality, multilabe },
}