TR04-051 Authors: Zdenek Dvorák, Daniel Král, Ondrej Pangrác

Publication: 18th June 2004 16:56

Downloads: 953

Keywords:

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, $\rho_l(\Pi)$ denotes the largest ratio of constraints which can be satisfied in any $l$-consistent instance composed by constraints from the set $\Pi$. In the general

case of sets $\Pi$ consisting of finitely many Boolean predicates,

we express the limit $\rho_{\infty}(\Pi):=\lim\limits_{l\to\infty}\rho_l(\Pi)$

as the minimum of a certain functional on a convex set of polynomials.

Our technique yields a robust deterministic algorithm (for a fixed

set $\Pi$) running in time linear in the size of the input and

$1/\varepsilon$ which finds either an inconsistent set of constraints

(of size bounded by the function of $\varepsilon$) or a truth

assignment which satisfies the fraction of at least $\rho_{\infty}(\Pi)-\varepsilon$ of the given constraints.

In addition, we compute the values of $\rho_l(\{P\})$ for every predicate $P$ which has arity at most three or which is $1$-extendable.