How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?

Kód výsledku v IS VaVaI

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

Výsledek na webu

<a href="http://dx.doi.org/10.1007/978-3-319-14612-6_5" target="_blank" >http://dx.doi.org/10.1007/978-3-319-14612-6_5</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/978-3-319-14612-6_5" target="_blank" >10.1007/978-3-319-14612-6_5</a>

Jazyk výsledku

angličtina

Název v původním jazyce

How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?

Popis výsledku v původním jazyce

An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniformmetric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.

Název v anglickém jazyce

How Hard Is the LP Relaxation of the Potts Min-Sum Labeling Problem?

Popis výsledku anglicky

An important subclass of the min-sum labeling problem (also known as discrete energy minimization or valued constraint satisfaction) is the pairwise min-sum problem with arbitrary unary costs and attractive Potts pairwise costs (also known as the uniformmetric labeling problem). In analogy with our recent result, we show that solving the LP relaxation of the Potts min-sum problem is not significantly easier than that of the general min-sum problem and thus, in turn, the general linear program. This suggests that trying to find an efficient algorithm to solve the LP relaxation of the Potts min-sum problem has a fundamental limitation. Our constructions apply also to integral solutions, yielding novel reductions of the (non-relaxed) general min-sum problem to the Potts min-sum problem.

Druh

D - Stať ve sborníku

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 statě ve sborníku

EMMCVPR 2015: Proceedings of the 10th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition

ISBN

978-3-319-14611-9

ISSN

0302-9743

e-ISSN

—

Počet stran výsledku

14

Strana od-do

57-70

Název nakladatele

Springer

Místo vydání

Heidelberg

Místo konání akce

Hong Kong

Datum konání akce

13. 1. 2015

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000357502000005