Simulated Annealing in Convex Bodies and an O*(n4) Volume Algorithm

Efficient volume computation in high dimension is an important question both theoretically and practically. The first polynomial time randomized algorithm to compute the volume of a convex body in Rn was given by Dyer, Frieze and Kannan in their pathbreaking paper [3]. A very high power of the dimension n (about 26) occurred in the running time bound of this algorithm, but subsequent improvements brought the exponent down to 5 [7]. In this paper, we further improve the running time to O¤(n4) (where the asterisk means that we suppress factors that are logarithmic in n). The algorithm uses O¤(n) points for its computations, and in this sense it is nearly optimal, since any algorithm must use ­(n) points.