approximation_class (492B)
1 # Approximation classes 2 3 - [FPRAS]: for all epsilon you have an [algorithm_randomized] running in polynomial time in 1/e and in the input, with a probability delta of failure 4 - variant [QPRAS] with [quasi-polynomial] time 5 - [PRAS]: same but not polynomial in 1/e 6 - without R, a deterministic algorithm ([PRAS] vs [PTAS], [FPRAS] vs [FPTAS]) 7 - [APX]: there is an [approximation_algorithm] for a certain fixed epsilon 8 9 Up: [complexity_class] of [approximation] 10 11 See also: [complexity_random]