Digitale Medien
Springer
Mathematical programming
86 (1999), S. 443-461
ISSN:
1436-4646
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract. It is shown that the “hit-and-run” algorithm for sampling from a convex body 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 bound for other sampling algorithms. We show that the bound is best possible in terms of R,r and n.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/s101070050099
Permalink
Bibliothek |
Standort |
Signatur |
Band/Heft/Jahr |
Verfügbarkeit |