Universality of the local marginal polytope
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Universality of the local marginal polytope
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
JD - Use of computers, robotics and its application
OECD FORD branch
—
Result continuities
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)
Others
Publication year
2015
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Name of the periodical
IEEE Transactions on Pattern Analysis and Machine Intelligence
ISSN
0162-8828
e-ISSN
—
Volume of the periodical
37
Issue of the periodical within the volume
4
Country of publishing house
US - UNITED STATES
Number of pages
7
Pages from-to
898-904
UT code for WoS article
000351213400015
EID of the result in the Scopus database
2-s2.0-84924567243