Convex Volume Approximation

In the analysis of algorithms, convex volume approximation concerns the computation of the volume of high-dimensional convex bodies, a problem that also models several problems in combinatorial enumeration. Because listing a convex body's vertices or faces explicitly is impractical in high dimensions, researchers typically work in a black-box model where a subroutine merely tests whether a given point lies inside or outside the body; in this model no deterministic algorithm can achieve an accurate approximation, and the problem remains sharp-P-hard even given explicit vertex or face data. Martin Dyer, Alan M. Frieze and Ravindran Kannan nonetheless developed a randomized polynomial-time approximation scheme for the problem, showing that randomization succeeds where deterministic computation cannot.