Volume computation: a status report
Markov Chains in Algorithms and Statistical Physics
February 03, 2005 09:30 AM to 10:30 AM
Speakers:
Lovász, László
|
 |
Abstract: |
In 1989, Dyer, Frieze and Kannan designed the first polynomial time
randomized algorithm to approximate the volume of a convex body $K$ in
$\R^n$. A crucial step of the algorithm is to generate a random point
in a convex body, which is achieved by making a random walk inside the
body. Their original algorithm had complexity about $n^{23}$; since
then, improvements in the walk itself, in the methods bounding the
mixing time, in the isoperimetric inequalities that provide the
geometric background, and in the preprocessing algorithms brought the
exponent down to (essentially) 4.
The talk will sketch some of the key ideas and also point out several
interesting problems that are still open.
|
|
|
