file.pdf (3.77 MB)
Download file

Computing the volume of convex bodies : a case where randomness provably helps

Download (3.77 MB)
journal contribution
posted on 01.01.1991, 00:00 by Martin Dyer, Frieze
Abstract: "We discuss the problem of computing the volume of a convex body K in R[superscript n]. We review worst-case results which show that it is hard to deterministically approximate vol[subscript n]K and randomised approximation algorithms which show that with randomisation one can approximate very nicely. We then provide some applications of this latter result."


Publisher Statement

All Rights Reserved



Usage metrics