Universality of the local marginal polytope

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F15%3A00229476" target="_blank" >RIV/68407700:21230/15:00229476 - isvavai.cz</a>

Výsledek na webu

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

DOI - Digital Object Identifier

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

Jazyk výsledku

angličtina

Název v původním jazyce

Universality of the local marginal polytope

Popis výsledku v původním jazyce

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

Název v anglickém jazyce

Universality of the local marginal polytope

Popis výsledku anglicky

We show that solving the LP relaxation of the min-sum labeling problem (also known as MAP inference problem in graphical models, discrete energy minimization, or valued constraint satisfaction) is not easier than solving any linear program. Precisely, every polytope is linear-time representable by a local marginal polytope and every LP can be reduced in linear time to a linear optimization (allowing infinite costs) over a local marginal polytope. The reduction can be done (though with a higher time complexity) even if the local marginal polytope is restricted to have a planar structure.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

JD - Využití počítačů, robotika a její aplikace

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

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

Rok uplatnění

2015

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

—

Svazek periodika

37

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

US - Spojené státy americké

Počet stran výsledku

7

Strana od-do

898-904

Kód UT WoS článku

000351213400015

EID výsledku v databázi Scopus

2-s2.0-84924567243