Convex volume approximation


In the analysis of algorithms, several authors have studied the computation of the volume of high-dimensional convex bodies, a problem that can also be used to model many other problems in combinatorial enumeration.
Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a convex polytope.
It is known that, in this model, no deterministic algorithm can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard.
However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized polynomial time approximation scheme for the problem,
providing a sharp contrast between the capabilities of randomized and deterministic algorithms.
The main result of the paper is a randomized algorithm for finding an approximation to the volume of a convex body in -dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in, the dimension of and.
The algorithm combines two ideas:
The given convex body can be approximated by a sequence of nested bodies, eventually reaching one of known volume, with this approach used to estimate the factor by which the volume changes at each step of this sequence. Multiplying these factors gives the approximate volume of the original body.
This work earned its authors the 1991 Fulkerson Prize.

Improvements

Although the time for this algorithm is polynomial, it has a high exponent.
Subsequent authors improved the running time of this method by providing more quickly mixing Markov chains for the same problem.

Generalizations

The polynomial-time approximability result has been generalized to more complex structures such as the union and intersection of objects. This relates to Klee's measure problem.