Computer Science – Discrete Mathematics
Scientific paper
2011-09-06
Computer Science
Discrete Mathematics
9 pages, 0 figures; Control Systems and Computers #2/2011, Special issue: "Optimal Labeling Problem in Structural Pattern Reco
Scientific paper
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 sufficient 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 sufficient 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.
Hlavac Vaclav
Shekhovtsov Alexander
No associations
LandOfFree
On Partial Opimality by Auxiliary Submodular Problems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with On Partial Opimality by Auxiliary Submodular Problems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On Partial Opimality by Auxiliary Submodular Problems will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-93419