= Fully polynomial randomized approximation scheme
{title2=$\mathbb P((1-\varepsilon)Z\leq\widehat Z\leq(1+\varepsilon)Z)\geq1-\delta$}
= FPRAS
{c}
{synonym}
For a nonnegative counting quantity $Z$, an FPRAS is a <randomized algorithm> with the displayed guarantee, running in time polynomial in encoded input length, $\varepsilon^{-1}$ and $\log(\delta^{-1})$. The usual constant-success definition is equivalent by independent repetition and a median. This counting notion differs from a deterministic <fully polynomial-time approximation scheme> for optimization.
Back to article page
