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 (2026a) 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 (2026a) credit GPT-6 Astra with an initial rapid-mixing proof, and ChatGPT with finding the subsequent counting scheme; the authors generalized and rewrote these arguments.

Chen and Liu (2026b) also gave a scheme for mixed volume.

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 2026a. https://arxiv.org/abs/2610.06724.Chen, X. and Liu, K. "An FPRAS for Mixed Volumes." 1 Nov 2026b. https://arxiv.org/abs/2611.01368v1.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