Publication details
Locally consistent constraint satisfaction problems
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | Theoretical Computer Science |
| Citation | |
| Doi | http://dx.doi.org/10.1016/j.tcs.2005.09.012 |
| Keywords | constraint satisfaction problems; Boolean predicates; CNF formulas; 2-SAT |
| Description | 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. |