Loading…
Robust Satisfiability for CSPs: Hardness and Algorithmic Results
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 satisfiabl...
Saved in:
| Published in: | ACM transactions on computation theory 2013-11, Vol.5 (4), p.1-25 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|---|
| ISSN: | 1942-3454 1942-3462 |
| DOI: | 10.1145/2540090 |