hasApproximationGuarantee
P145842
predicate
Indicates that there exists a formal bound on how close a solution or outcome is to the optimal one.
Observed surface forms (1)
- approximationGuarantee ×1
Sample triples (2)
| Subject | Object |
|---|---|
| LLL algorithm | produces basis with reasonably short vectors via predicate surface "approximationGuarantee" ⓘ |
| Max-3-SAT | no polynomial-time algorithm can beat 7/8 + ε under P≠NP (for some formulations) ⓘ |