approximation_class (536B)
1 # Approximation classes 2 3 - FPRAS [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 [qpras] with "quasi-polynomial time" [quasipolynomial] 5 - PRAS [pras]: same but not polynomial in 1/e 6 - without R, a deterministic algorithm (PRAS vs PTAS [ptas], FPRAS vs FPTAS [fptas]) 7 - APX [apx]: there is an approximation algorithm for a certain fixed epsilon 8 9 Up: [complexity_class] of [approximation] 10 11 See also: [complexity_random]