On the randomized complexity of volume and diameter

Publisher Website
Google Scholar
Abstract
The authors give an O(n/sup 7/log/sup 2/n) randomised algorithm to approximate the volume of a convex body, and an O(n/sup 6/log n) algorithm to sample a point from the uniform distribution over a convex body. For convex polytopes the algorithm runs in O(n/sup 7/log/sup 4/n) steps. Several tools are developed that may be interesting on their own. They extend results of Sinclair-Jerrum (1988) and the authors (1990) on the mixing rate of Markov chains from finite to arbitrary Markov chains. They describe an algorithm to integrate a function with respect to the stationary distribution of a general Markov chain. They also analyze the mixing rate of various random walks on convex bodies, in particular the random walk with steps from the uniform distribution over a unit ball. In several previous positive and negative results, the problem of computing the diameter of a convex body behaved similarly as the volume problem. In contrast to this, they show that there is no polynomial randomized algorithm to compute the diameter within a factor of n/sup 1/4/.

This publication has 12 references indexed in Scilit: