Limit behavior of locally consistent constraint satisfaction problems
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216208%3A11320%2F11%3A10100274" target="_blank" >RIV/00216208:11320/11:10100274 - isvavai.cz</a>
Výsledek na webu
<a href="http://dx.doi.org/10.1137/060667591" target="_blank" >http://dx.doi.org/10.1137/060667591</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1137/060667591" target="_blank" >10.1137/060667591</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Limit behavior of locally consistent constraint satisfaction problems
Popis výsledku v původním jazyce
We study the limit ratio of constraints that can be simultanously satisfied in an instance of given CSP type under the assumption that every subinstance with at most a given number of constraints is fully satisfiable. As a consequence of our structural results, we obtain an approximation algorithm that finds an assignment with the number of constraints satisfied close to the limit.
Název v anglickém jazyce
Limit behavior of locally consistent constraint satisfaction problems
Popis výsledku anglicky
We study the limit ratio of constraints that can be simultanously satisfied in an instance of given CSP type under the assumption that every subinstance with at most a given number of constraints is fully satisfiable. As a consequence of our structural results, we obtain an approximation algorithm that finds an assignment with the number of constraints satisfied close to the limit.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Ostatní
Rok uplatnění
2011
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ů
Údaje specifické pro druh výsledku
Název periodika
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Svazek periodika
25
Číslo periodika v rámci svazku
2
Stát vydavatele periodika
US - Spojené státy americké
Počet stran výsledku
18
Strana od-do
916-933
Kód UT WoS článku
000292302000030
EID výsledku v databázi Scopus
—