Go backward to 11 Minimum TriangulationGo up to 2 Coordinate DescriptionsGo forward to 13 Largest/Smallest j-Simplex |
XHTML 1.0 |

Input: | Polytope P in H-description |
---|---|

Output: | The volume of P |

Status (general): | #P-hard, FPRAS |
---|---|

Status (fixed dim.): | Polynomial time |

Dyer and Frieze [15] showed that the general problem is
#P-hard (and #P-easy as well). Dyer, Frieze, and
Kannan [16] found a Fully Polynomial Randomized
Approximation Scheme (FPRAS) for the problem, i.e., a
family (A of randomized
algorithms, where, for each _{ε})_{ε>0}ε> 0, A
computes a number _{ε}V with the property that the
probability of _{ε}(1-ε) vol(P) ≤ V is at least _{ε} ≤ (1+ε) vol(P)3/4, and the
running times of the algorithms A are bounded by a
polynomial in the input size and _{ε}1/ε.
For fixed dimension, one can first compute all vertices of The complexity status of the analogue problem with the polytope
specified by a |

Why are some symbols not displayed correctly? |