Electronic Resource
Springer
Mathematical programming
86 (1999), S. 443-461
ISSN:
1436-4646
Source:
Springer Online Journal Archives 1860-2000
Topics:
Computer Science
,
Mathematics
Notes:
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.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/s101070050099
Permalink
| Library |
Location |
Call Number |
Volume/Issue/Year |
Availability |
