On Partial Opimality by Auxiliary Submodular Problems
On Partial Opimality by Auxiliary Submodular Problems
复制标题
关于辅助子模问题的部分最优性
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Václav Hlaváč
中科院分区：
文献类型：
--
作者：
A. Shekhovtsov;Václav Hlaváč
在这项工作中，我们证明了三种不同的能量最小化技术之间的几种关系。Ivan Kovtun （IK）、线性规划松弛法（LP）和Yuri Boykov （Yuri Boykov）最近提出的确定可证明的最优变量部分分配的方法。提出了一种新的基于LP松弛的最优部分分配的充分条件，称为LP自闭性。我们证明了构造辅助子模问题的Kovtun方法满足这个充分条件。这样就建立了以下联系：腰压松弛不能被IK收紧。对于非次模问题，这是一个非平凡的结果。在两个标签的情况下，LP松弛提供了最优的部分分配，称为持久性，正如我们所示，它优于IK。将IK与扩展移动联系起来，我们证明了对于初始问题具有任何“截断”规则的扩展移动不动点集与IK的一对一方法所限制的问题是重合的，即该方法不能改进扩展移动。在两个标签的情况下，具有特定截断规则的扩展移动与“一对全”方法一致。
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.