Robust satisfiability for CSPs: hardness and algorithmic results

DOI10.1145/2540090MaRDI QIDQ2947586zbMATH OpenOpenAlexFDO

Authors Víctor Dalmau, Andrei Krokhin

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)

Recommendations

• Robust satisfiability of constraint satisfaction problems
• Robustly solvable constraint satisfaction problems
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Linear programming, width-1 CSPs, and robust satisfaction
• Robust algorithms with polynomial loss for near-unanimity CSPs

Cited in

(20)

• Linear programming, width-1 CSPs, and robust satisfaction
• The power of linear programming for general-valued CSPs
• Robust algorithms with polynomial loss for near-unanimity CSPs
• scientific article; zbMATH DE number 7359806 (Why is no real title available?)
• The power of Sherali-Adams relaxations for general-valued CSPs
• Complexity of approximating CSP with balance/hard constraints
• CLAP: A New Algorithm for Promise CSPs
• The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
• Robust satisfiability of constraint satisfaction problems
• Sherali-Adams relaxations for valued CSPs
• Solving CSPs using weak local consistency
• A new line of attack on the dichotomy conjecture
• Towards a characterization of constant-factor approximable finite-valued CSPs
• Reformulation based MaxSat robustness
• The complexity of valued CSPs
• Robustly solvable constraint satisfaction problems
• On algebras with many symmetric operations
• Robust algorithms with polynomial loss for near-unanimity CSPs
• Robust algorithms for restricted domains
• Gap theorems for robust satisfiability: Boolean CSPs and beyond

This page was built for publication: Robust satisfiability for CSPs: hardness and algorithmic results

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2947586)