Publication details
LIMIT BEHAVIOR OF LOCALLY CONSISTENT CONSTRAINT SATISFACTION PROBLEMS
| Authors | |
|---|---|
| Year of publication | 2011 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/060667591 |
| Keywords | constraint satisfaction problem (CSP); local consistency |
| Description | 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. |