@Article{shekhovtsov-11-aux_submodular,
 IS = { zkontrolovano 01 Aug 2011 },
 UPDATE  = { 2011-08-01 },
 author = {Shekhovtsov, Alexander and Hlav{\'a}{\v c}, V{\' a}clav},
 title = {On Partial Opimality by Auxiliary Submodular Problems},
 journal ={Control Systems and Computers},
 year = {2011},
 number = {2},
 volume = {232},
 pages = {71-78},
 project  = { FP7-ICT-247870 NIFTi, 1M0567 },
 issn = {0130-5395},
 note = {Special Issue},
 publisher = {National Academy of Science of Ukraine},
 address = {Glushkova 40, 04680 GSP Kiev, Ukraine},
 annote = {In this work, we prove several relations between three
   different energy minimization techniques. A recently proposed
   methods for determining a provably optimal partial assignment of
   variables by Ivan Kovtun (IK), the linear programming relaxation
   approach (LP) and the popular expansion move algorithm by Yuri
   Boykov.  We propose a novel suffcient condition of optimal partial
   assignment, which is based on LP relaxation and called LP-autarky.
   We show that methods of Kovtun, which build auxiliary submodular
   problems, fulfill this suffcient condition. The following link is
   thus established: LP relaxation cannot be tightened by IK. For
   non-submodular problems this is a non-trivial result.  In the case
   of two labels, LP relaxation provides optimal partial assignment,
   known as persistency, which, as we show, dominates IK. Relating IK
   with expansion move, we show that the set of fixed points of
   expansion move with any "truncation" rule for the initial problem
   and the problem restricted by one-vs-all method of IK would
   coincide - i.e. expansion move cannot be improved by this
   method. In the case of two labels, expansion move with a particular
   truncation rule coincide with one-vs-all method.},
keywords    = { energy minimization, MRF,relaxation, persistance, 
  partial optimality, domain constraints, autarky, expansion-move },
}