Robust satisfiability of constraint satisfaction problems

DOI10.1145/2213977.2214061zbMath1286.68178OpenAlexW2063711222MaRDI QIDQ5415526

Marcin Kozik, Libor Barto

Publication date: 13 May 2014

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

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

zbMATH Keywords

approximationconstraint satisfaction problemuniversal algebrabounded widthrobust satisfiability

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) 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) Approximation algorithms (68W25)

Related Items (13)

Sherali-Adams Relaxations for Valued CSPs ⋮ Constraint Satisfaction Problems Solvable by Local Consistency Methods ⋮ On the complexity of \(\mathbb{H}\)-coloring for special oriented trees ⋮ Unnamed Item ⋮ On finite Taylor algebras ⋮ A new line of attack on the dichotomy conjecture ⋮ The Complexity of Valued CSPs ⋮ Unnamed Item ⋮ On algebras with many symmetric operations ⋮ Deciding absorption ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Solving CSPs Using Weak Local Consistency ⋮ Unnamed Item

This page was built for publication: Robust satisfiability of constraint satisfaction problems