An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems

KRÁĽ, Daniel and O PANGRAC. An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems. MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS. BERLIN: SPRINGER-VERLAG BERLIN, 2005, vol. 3618, p. 603-614. ISSN 0302-9743.

Basic information

Original name

An asymptotically optimal linear-time algorithm for locally consistent constraint satisfaction problems

Authors

KRÁĽ, Daniel and O PANGRAC

Edition

MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE 2005, PROCEEDINGS, BERLIN, SPRINGER-VERLAG BERLIN, 2005, 0302-9743

---

Other information

Language

English

Type of outcome

Article in a journal

Confidentiality degree

is not subject to a state or trade secret

UT WoS

000232273200052

---

Abstract

In the original language

An instance of a constraint satisfaction problem is l-consistent if any l constraints of it can be simultaneously satisfied. For a set II of constraint types, p(l)(II) denotes the largest ratio of constraints which can be satisfied in any l-consistent instance composed by constraints from the set II. We study the asymptotic behavior of p(l)(II) for sets II consisting of Boolean predicates. The value p(infinity)(II) := (l ->infinity) lim p(l) (II) is determined for all such sets II. Moreover, we design a robust deterministic algorithm (for a fixed set II of predicates) running in time linear in the size of the input and 1/epsilon which finds either an inconsistent set of constraints (of size bounded by the function of epsilon) or a truth assignment which satisfies the fraction of at least p(infinity)(II)-epsilon of the given constraints. Most of our results hold for both the unweighted and weighted versions of the problem.