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 problemhomomorphism dualityuniversal algebra

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

(24)

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

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)