ECCC-Report TR04-051https://eccc.weizmann.ac.il/report/2004/051Comments and Revisions published for TR04-051en-usFri, 18 Jun 2004 16:56:32 +0300
Paper TR04-051
| Locally consistent constraint satisfaction problems |
Zdenek Dvorák,
Daniel Král,
Ondrej Pangrác
https://eccc.weizmann.ac.il/report/2004/051An 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.
Fri, 18 Jun 2004 16:56:32 +0300https://eccc.weizmann.ac.il/report/2004/051