Hit-and-run mixes fast

Authors
Citation
L. Lovasz, Hit-and-run mixes fast, MATH PROGR, 86(3), 1999, pp. 443-461
Citations number
13
Language
INGLESE
art.tipo
Article
Categorie Soggetti
Mathematics
Journal title
MATHEMATICAL PROGRAMMING
ISSN journal
0025-5610 → ACNP
Volume
86
Issue
3
Year of publication
1999
Pages
443 - 461
Database
ISI
SICI code
0025-5610(199912)86:3<443:HMF>2.0.ZU;2-H
Abstract
It is shown that the "hit-and-run" algorithm for sampling from a convex bod y K (introduced by R.L. Smith) mixes in time O*(n(2)R(2)/r(2)), where R and r are the radii of the inscribed and circumscribed balls of K. Thus after appropriate preprocessing, hit-and-run produces an approximately uniformly distributed sample point in time O*(n(3)), which matches the best known bou nd for other sampling algorithms. We show that the bound is best possible i n terms of R, r and n.