file.pdf (3.77 MB)

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."

History

Publisher Statement

All Rights Reserved

Date

01/01/1991

Usage metrics

Exports