TOPICS
Search

Fully Polynomial-Time Randomized Approximation Scheme

A fully polynomial-time randomized approximation scheme, abbreviated FPRAS, is a randomized algorithm that, given an input x and 0<epsilon<1, returns an estimate f^^(x) of a nonnegative quantity f(x) satisfying

Pr[(1-epsilon)f(x)<=f^^(x)<=(1+epsilon)f(x)]>=3/4

in time bounded by a polynomial in the input length and 1/epsilon. Independent repetitions can increase the success probability (Jerrum et al. 1986, §6).

Chen and Liu (2026) gave such a scheme for counting common matroid bases of two matroids on a common ground set, given by independence oracles. An independence oracle decides whether a specified subset is independent. They also gave an algorithm running in polynomial time for approximately uniform sampling of common matroid bases when at least one common matroid basis exists. Chen and Liu (2026) report extensive AI assistance in developing their proof ideas.

See also

Algorithm, Polynomial Time, Randomized Algorithm

Explore with Wolfram|Alpha

References

Chen, X. and Liu, K. "An FPRAS for Counting Common Bases of Two Matroids." 5 Oct 2026. https://arxiv.org/abs/2610.06724.Jerrum, M. R.; Valiant, L. G.; and Vazirani, V. V. "Random Generation of Combinatorial Structures from a Uniform Distribution." Theoret. Comput. Sci. 43, 169-188, 1986. https://doi.org/10.1016/0304-3975(86)90174-X.

Cite this as:

Weisstein, Eric W. "Fully Polynomial-Time Randomized Approximation Scheme." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/FullyPolynomial-TimeRandomizedApproximationScheme.html

Subject classifications