Informace o publikaci
LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS
| Autoři | |
|---|---|
| Rok publikování | 2011 |
| Druh | Článek v odborném periodiku |
| Citace | |
| Doi | http://dx.doi.org/10.1137/060667591 |
| Klíčová slova | constraint satisfaction problem (CSP); local consistency |
| Popis | 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. |