Editing Polynomial-time approximation scheme (section)

===Randomized===
Some problems which do not have a PTAS may admit a [[randomized algorithm]] with similar properties, a '''polynomial-time randomized approximation scheme''' or '''PRAS'''.  A PRAS is an algorithm which takes an instance of an optimization or counting problem and a parameter {{math|ε > 0}} and, in polynomial time, produces a solution that has a ''high probability'' of being within a factor {{math|ε}} of optimal.  Conventionally, "high probability" means probability greater than 3/4, though as with most probabilistic complexity classes the definition is robust to variations in this exact value (the bare minimum requirement is generally greater than 1/2).  Like a PTAS, a PRAS must have running time polynomial in {{mvar|n}}, but not necessarily in {{math|ε}}; with further restrictions on the running time in {{math|ε}}, one can define an '''efficient polynomial-time randomized approximation scheme''' or '''EPRAS''' similar to the EPTAS, and a '''fully polynomial-time randomized approximation scheme''' or '''FPRAS''' similar to the FPTAS.<ref name="vvv">{{cite book
  | last = Vazirani
  | first = Vijay V.
  | title = Approximation Algorithms
  | publisher = Springer
  | year = 2003
  | pages = 294–295
  | location = Berlin
  | isbn = 3-540-65367-8
}}</ref>