Locally consistent constraint satisfaction problems

J 2005

Locally consistent constraint satisfaction problems

DVORAK, Z; Daniel KRÁĽ a O PANGRAC

Základní údaje

Originální název

Locally consistent constraint satisfaction problems

Autoři

DVORAK, Z; Daniel KRÁĽ a O PANGRAC

Vydání

Theoretical Computer Science, AMSTERDAM, North Holland, 2005, 0304-3975

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

Impakt faktor

Impact factor: 0.743

DOI

https://doi.org/10.1016/j.tcs.2005.09.012

UT WoS

000233671500004

Klíčová slova anglicky

constraint satisfaction problems; Boolean predicates; CNF formulas; 2-SAT

Změněno: 6. 11. 2020 10:58, Mgr. Darina Boukalová

Anotace

V originále

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set pi of constraint types, p(l)(pi) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from pi. In the case of sets pi consisting of finitely many Boolean predicates, we express the limit p(infinity)(pi) : =lim(l) p(l)(pi) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set pi) running in time linear in the size of the input and I/epsilon which finds either an inconsistent set of constraints (of size bounded by the function of F,) or a truth assignment which satisfies the fraction of at least p(infinity) (pi)-epsilon of the given constraints. We also compute the values of p(l) ({P}) for several specific predicates P. (c) 2005 Elsevier B.V. All rights reserved.

Citovat

DVORAK, Z; Daniel KRÁĽ a O PANGRAC. Locally consistent constraint satisfaction problems. Theoretical Computer Science. AMSTERDAM: North Holland, 2005, roč. 348, 2-3, s. 187-206. ISSN 0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2005.09.012.

@article{1689749,
   author = {Dvorak, Z and Kráľ, Daniel and Pangrac, O},
   article_location = {AMSTERDAM},
   article_number = {2-3},
   doi = {https://doi.org/10.1016/j.tcs.2005.09.012},
   keywords = {constraint satisfaction problems; Boolean predicates; CNF formulas; 2-SAT},
   language = {eng},
   issn = {0304-3975},
   journal = {Theoretical Computer Science},
   title = {Locally consistent constraint satisfaction problems},
   volume = {348},
   year = {2005}
}

TY  - JOUR
ID  - 1689749
AU  - Dvorak, Z - Kráľ, Daniel - Pangrac, O
PY  - 2005
TI  - Locally consistent constraint satisfaction problems
JF  - Theoretical Computer Science
VL  - 348
IS  - 2-3
SP  - 187-206
EP  - 187-206
PB  - North Holland
SN  - 03043975
KW  - constraint satisfaction problems
KW  - Boolean predicates
KW  - CNF formulas
KW  - 2-SAT
N2  - An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set pi of constraint types, p(l)(pi) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints of types from pi. In the case of sets pi consisting of finitely many Boolean predicates, we express the limit p(infinity)(pi) : =lim(l) p(l)(pi) as the minimum of a certain functional on a convex set of polynomials. Our results yield a robust deterministic algorithm (for a fixed set pi) running in time linear in the size of the input and I/epsilon which finds either an inconsistent set of constraints (of size bounded by the function of F,) or a truth assignment which satisfies the fraction of at least p(infinity) (pi)-epsilon of the given constraints. We also compute the values of p(l) ({P}) for several specific predicates P. (c) 2005 Elsevier B.V. All rights reserved.
ER  -

DVORAK, Z; Daniel KRÁĽ a O PANGRAC. Locally consistent constraint satisfaction problems. \textit{Theoretical Computer Science}. AMSTERDAM: North Holland, 2005, roč.~348, 2-3, s.~187-206. ISSN~0304-3975. Dostupné z: https://doi.org/10.1016/j.tcs.2005.09.012.

Přehled o publikaci