Go backward to 11 Minimum Triangulation
Go up to 2 Coordinate Descriptions
Go forward to 13 Largest/Smallest j-Simplex
|
Go backward to 11 Minimum Triangulation Go up to 2 Coordinate Descriptions Go 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ε)ε>0 of randomized
algorithms, where, for each ε> 0, Aε
computes a number Vε with the property that the
probability of (1-ε) vol(P) ≤ Vε ≤ (1+ε) vol(P) is at least 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 P (see Problem 1) and its face lattice (see Problem 5) both in polynomial time. Then one can construct some triangulation (see Problem 11) of P (e.g., its barycentric subdivision) in polynomial time and compute the volume of P as the sum of the volumes of the (maximal) simplices in the triangulation. The complexity status of the analogue problem with the polytope specified by a V-description is the same. |
|
|
Why are some symbols not displayed correctly? |