Dalmau, V. and Krokhin, A. (2013) 'Robust satisfiability for CSPs : hardness and algorithmic results.', ACM transactions on computation theory., 5 (4). p. 15.
An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such that at most a ε-fraction of constraints needs to be removed to make the instance satisfiable), where f(ε) → 0 as ε → 0. We establish an algebraic framework for analyzing constraint satisfaction problems admitting an efficient robust algorithm with functions f of a given growth rate. We use this framework to derive hardness results. We also describe three classes of problems admitting an efficient robust algorithm such that f is O(1/log (1/ε)), O(ε1/k) for some k > 1, and O(ε), respectively. Finally, we give a complete classification of robust satisfiability with a given f for the Boolean case.
|Full text:||(AM) Accepted Manuscript|
Download PDF (198Kb)
|Publisher Web site:||http://dx.doi.org/10.1145/2540090|
|Publisher statement:||© ACM 2013. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ACM Transactions on Computation Theory, 5, 4, 15, 2013, http://dx.doi.org/10.1145/2540090.|
|Date accepted:||No date available|
|Date deposited:||06 June 2014|
|Date of first online publication:||November 2013|
|Date first made open access:||No date available|
Save or Share this output
|Look up in GoogleScholar|