Informace o publikaci
Locally consistent constraint satisfaction problems - (Extended abstract)
| Autoři | |
|---|---|
| Rok publikování | 2004 |
| Druh | Článek v odborném periodiku |
| Časopis / Zdroj | AUTOMATA , LANGUAGES AND PROGRAMMING, PROCEEDINGS |
| Citace | |
| Popis | An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a fixed constraint type P, rho(l)(P) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance. In this paper, we study locally consistent constraint satisfaction problems for constraints which are Boolean predicates. We determine the values of rho(l)(P) for all I and all Boolean predicates which have a certain natural property which we call 1-extendibility as well as for all Boolean predicates of arity at most three. All our results hold for both the unweighted and weighted versions of the problem. |