On Partial Opimality by Auxiliary Submodular Problems

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F11%3A00181662" target="_blank" >RIV/68407700:21230/11:00181662 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

On Partial Opimality by Auxiliary Submodular Problems

Original language description

We prove several relations between 3 energy minimization techniques. 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 algorithmby 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. Thefollowing 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.

Czech name

—

Czech description

—

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

JD - Use of computers, robotics and its application

OECD FORD branch

—

Project

Result was created during the realization of more than one project. More information in the Projects tab.

Continuities

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Publication year

2011

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Control Systems and Computers

ISSN

0130-5395

e-ISSN

—

Volume of the periodical

232

Issue of the periodical within the volume

2

Country of publishing house

UA - UKRAINE

Number of pages

8

Pages from-to

71-78

UT code for WoS article

—

EID of the result in the Scopus database

—