All reports by Author Ondrej Pangrác:

__
TR04-051
| 10th June 2004
__

Zdenek Dvorák, Daniel Král, Ondrej Pangrác#### Locally consistent constraint satisfaction problems

Zdenek Dvorák, Daniel Král, Ondrej Pangrác

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 ...
more >>>