The complexity of maximal constraint languages

DOI10.1145/380752.380868zbMath1323.68294OpenAlexW2049197377MaRDI QIDQ5176025

Andrei A. Krokhin, Andrei A. Bulatov, Peter G. Jeavons

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380868

zbMATH Keywords

complexityNP-completenessrelational clonetractabilityconstraint languagealgebraic invariance propertyconstraint satisfaciton problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Tractability in constraint satisfaction problems: a survey ⋮ A Galois Connection for Valued Constraint Languages of Infinite Size ⋮ Necessary Conditions for Tractability of Valued CSPs ⋮ The complexity of soft constraint satisfaction ⋮ Rigid binary relations on a 4-element domain ⋮ Tractable structures for constraint satisfaction with truth tables ⋮ Recognizing frozen variables in constraint satisfaction problems ⋮ Combinatorial problems raised from 2-semilattices ⋮ Existentially restricted quantified constraint satisfaction ⋮ Maximal infinite-valued constraint languages ⋮ Basics of Galois Connections ⋮ Introduction to the Maximum Solution Problem ⋮ Periodic constraint satisfaction problems: Tractable subclasses

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)