LP Relaxation of the Potts Labeling Problem Is as Hard as Any Linear Program

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F17%3A00312187" target="_blank" >RIV/68407700:21230/17:00312187 - isvavai.cz</a>

Výsledek na webu

<a href="http://ieeexplore.ieee.org/document/7494684/" target="_blank" >http://ieeexplore.ieee.org/document/7494684/</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1109/TPAMI.2016.2582165" target="_blank" >10.1109/TPAMI.2016.2582165</a>

Jazyk výsledku

angličtina

Název v původním jazyce

LP Relaxation of the Potts Labeling Problem Is as Hard as Any Linear Program

Popis výsledku v původním jazyce

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).

Název v anglickém jazyce

LP Relaxation of the Potts Labeling Problem Is as Hard as Any Linear Program

Popis výsledku anglicky

In our recent work, we showed that solving the LP relaxation of the pairwise min-sum labeling problem (also known as MAP inference in graphical models or discrete energy minimization) is not much easier than solving any linear program. Precisely, the general linear program reduces in linear time (assuming the Turing model of computation) to the LP relaxation of the min-sum labeling problem. The reduction is possible, though in quadratic time, even to the min-sum labeling problem with planar structure. Here we prove similar results for the pairwise min-sum labeling problem with attractive Potts interactions (also known as the uniform metric labeling problem).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

<a href="/cs/project/LL1303" target="_blank" >LL1303: Vyhledávání vizuálních kategorií ve velkém množství obrázků</a><br>

Návaznosti

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

Rok uplatnění

2017

Kód důvěrnosti údajů

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

Název periodika

IEEE Transactions on Pattern Analysis and Machine Intelligence

ISSN

0162-8828

e-ISSN

1939-3539

Svazek periodika

39

Číslo periodika v rámci svazku

7

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

7

Strana od-do

1469-1475

Kód UT WoS článku

000402744400016

EID výsledku v databázi Scopus

2-s2.0-85020294999