wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

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]