LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS

BODIRSKY, M a Daniel KRÁĽ. LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS. SIAM Journal on Discrete Mathematics. Philadelphia: SIAM, 2011, roč. 25, č. 2, s. 916-933. ISSN 0895-4801. Dostupné z: https://doi.org/10.1137/060667591.

Základní údaje

Originální název

LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS

Autoři

BODIRSKY, M a Daniel KRÁĽ

Vydání

SIAM Journal on Discrete Mathematics, Philadelphia, SIAM, 2011, 0895-4801

---

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.648

DOI

https://doi.org/10.1137/060667591

UT WoS

000292302000030

Klíčová slova anglicky

constraint satisfaction problem (CSP); local consistency

---

Anotace

V originále

An instance of a constraint satisfaction problem (CSP) is variable k-consistent if any sub-instance with at most k variables has a solution. For a fixed constraint language L, rho(k)(L) is the largest ratio such that any variable k-consistent instance has a solution that satisfies at least a fraction of rho(k)(L) of the constraints. We provide an expression for the limit rho(L) (sic) lim(k ->infinity)(L), and show that this limit coincides with the corresponding limit for constraint k-consistent instances, i.e., instances where all subinstances with at most k constraints have a solution. We also design an algorithm running in time polynomial in the size of input and 1/epsilon that for an input instance and a given e either computes a solution that satisfies at least a fraction of rho(L) - epsilon constraints or finds a set of inconsistent constraints whose size depends only on.. Most of our results apply both to weighted and to unweighted instances of the CSP.