Limit behavior of locally consistent constraint satisfaction problems

Abstract

We study the limit ratio of constraints that can be simultanously satisfied in an instance of given CSP type under the assumption that every subinstance with at most a given number of constraints is fully satisfiable. As a consequence of our structural results, we obtain an approximation algorithm that finds an assignment with the number of constraints satisfied close to the limit.

Keywords

• constraint satisfaction problems
• local consistency