Robust Satisfiability for CSPs

DOI10.1145/2540090zbMath1322.68099OpenAlexW2151577278MaRDI QIDQ2947586

Andrei A. Krokhin, Victor Dalmau

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

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

zbMATH Keywords

approximation algorithmsconstraint satisfaction problemuniversal algebrahomomorphism duality

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Related Items (14)

CLAP: A New Algorithm for Promise CSPs ⋮ Sherali-Adams Relaxations for Valued CSPs ⋮ Complexity of approximating CSP with balance/hard constraints ⋮ Towards a characterization of constant-factor approximable finite-valued CSPs ⋮ The Power of Sherali--Adams Relaxations for General-Valued CSPs ⋮ Unnamed Item ⋮ A new line of attack on the dichotomy conjecture ⋮ The Complexity of Valued CSPs ⋮ Unnamed Item ⋮ Robust Algorithms with Polynomial Loss for Near-Unanimity CSPs ⋮ Robustly Solvable Constraint Satisfaction Problems ⋮ On algebras with many symmetric operations ⋮ The Power of Linear Programming for General-Valued CSPs ⋮ Solving CSPs Using Weak Local Consistency

This page was built for publication: Robust Satisfiability for CSPs