Limit behavior of locally consistent constraint satisfaction problems
The result's identifiers
Result code in 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>
Result on the web
<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>
Alternative languages
Result language
angličtina
Original language name
Limit behavior of locally consistent constraint satisfaction problems
Original language description
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.
Czech name
—
Czech description
—
Classification
Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
BA - General mathematics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/1M0545" target="_blank" >1M0545: Institute for Theoretical Computer Science</a><br>
Continuities
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2011
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
SIAM Journal on Discrete Mathematics
ISSN
0895-4801
e-ISSN
—
Volume of the periodical
25
Issue of the periodical within the volume
2
Country of publishing house
US - UNITED STATES
Number of pages
18
Pages from-to
916-933
UT code for WoS article
000292302000030
EID of the result in the Scopus database
—