en>Giraffedata: comprised of

2013-02-18T04:10:32Z

New page

The paper is a joint work by [[Martin Dyer]], [[Alan M. Frieze]] and [[Ravindran Kannan]].<ref name=JACM91>
{{cite journal
|doi= 10.1145/102782.102783
|author= M.Dyer, A.Frieze and R.Kannan
|title=A random polynomial-time algorithm for approximating the volume of convex bodies
|journal= Journal of the ACM
|volume = 38
|issue =1
|pages =1–17
|year= 1991
|url=http://portal.acm.org/citation.cfm?id=102783}}
</ref>

The main result of the paper is a randomized algorithm for finding an <math>\epsilon</math> approximation to the volume of a convex body <math>K</math> in <math>n</math>-dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in <math>n</math>, the dimension of <math>K</math> and <math>1/\epsilon</math>.

The algorithm is a sophisticated usage of the so-called [[Markov chain Monte Carlo]] (MCMC) method.
The basic scheme of the algorithm is a nearly uniform sampling from within <math>K</math> by placing a grid consisting <math>n</math>-dimensional cubes and doing a [[random walk]] over these cubes. By using the theory of
[[Markov chain mixing time|rapidly mixing Markov chains]], they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.

==References==
<references/>

[[Category:Computational geometry]]
[[Category:Approximation algorithms]]

Poisson games - Revision history

en>Giraffedata: comprised of