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

KRÁĽ, Daniel a 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, roč. 3618, s. 603-614. ISSN 0302-9743.

Základní údaje

Originální název

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

Autoři

KRÁĽ, Daniel a O PANGRAC

Vydání

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

---

Další údaje

Jazyk

angličtina

Typ výsledku

Článek v odborném periodiku

Utajení

není předmětem státního či obchodního tajemství

UT WoS

000232273200052

---

Anotace

V originále

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.