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 $\varepsilon$ approximation to the volume of a convex body $K$ in $n$-dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in $n$, the dimension of $K$ and $1/\varepsilon$. The algorithm is a sophisticated usage of the so-called Markov chain Monte Carlo (MCMC) method. The basic scheme of the algorithm is a nearly uniform sampling from within $K$ by placing a grid consisting $n$-dimensional cubes and doing a random walk over these cubes. By using the theory of rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.

This work earned its authors the 1991 Fulkerson Prize. 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.