Robust satisfiability for CSPs: hardness and algorithmic results
From MaRDI portal
Publication:2947586
DOI10.1145/2540090zbMATH Open1322.68099OpenAlexW2151577278MaRDI QIDQ2947586FDOQ2947586
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
Recommendations
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
- Title not available (Why is that?)
- The power of Sherali-Adams relaxations for general-valued CSPs
- CLAP: A New Algorithm for Promise CSPs
- The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains
- Complexity of approximating CSP with balance/hard constraints
- 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
- Robust algorithms with polynomial loss for near-unanimity CSPs
- Robustly solvable constraint satisfaction problems
- On algebras with many symmetric operations
- 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)
