A practical problem with PTAS algorithms is that the exponent of the polynomial could increase dramatically as ε shrinks, for example if the runtime is O(n(1/ε)!).
One way of addressing this is to define the efficient polynomial-time approximation scheme or EPTAS, in which the running time is required to be O(nc) for a constant c independent of ε.
Even more restrictive, and useful in practice, is the fully polynomial-time approximation scheme or FPTAS, which requires the algorithm to be polynomial in both the problem size n and 1/ε.
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 n, but not necessarily in ε; with further restrictions on the running time in ε, 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.