Random walks and an O*(n5) volume algorithm for convex bodies
✍ Scribed by Ravi Kannan; László Lovász; Miklós Simonovits
- Publisher
- John Wiley and Sons
- Year
- 1997
- Tongue
- English
- Weight
- 423 KB
- Volume
- 11
- Category
- Article
- ISSN
- 1042-9832
No coin nor oath required. For personal study only.
✦ Synopsis
Given a high dimensional convex body K: ޒ n by a separation oracle, we can U Ž 5 . approximate its volume with relative error , using O n oracle calls. Our algorithm also brings the body into isotropic position. As all previous randomized volume algorithms, we Ž . use ''rounding'' followed by a multiphase Monte-Carlo product estimator technique. Both Ž . parts rely on sampling generating random points in K , which is done by random walk. Our Ž algorithm introduces three new ideas: the use of the isotropic position or at least an . Ž . approximation of it for rounding; the separation of global obstructions diameter and local Ž . obstructions boundary problems for fast mixing; and a stepwise interlacing of rounding and Ž .