Publication details
An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems
| Authors | |
|---|---|
| Year of publication | 2005 |
| Type | Article in Periodical |
| Magazine / Source | MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS |
| Citation | |
| Description | An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set II of constraint types, p(l)(II) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints from the set II. We study the asymptotic behavior of p(l)(II) for sets II consisting of Boolean predicates. The value p(infinity)(II) := (l ->infinity) lim p(l) (II) is determined for all such sets II. Moreover, we design a robust deterministic algorithm (for a fixed set II of predicates) running in time linear in the size of the input and 1/epsilon which finds either an inconsistent set of constraints (of size bounded by the function of epsilon) or a truth assignment which satisfies the fraction of at least p(infinity)(II)-epsilon of the given constraints. Most of our results hold for both the unweighted and weighted versions of the problem. |