School of Technology and Computer Science Seminars
A Random Polynomial Time Algorithm for Approximating The Volume of Convex Bodies
by Varun Narayanan (School of Technology and Computer Science, TIFR)
Friday, May 27, 2016
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
Description |
A randomized algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space was proposed by Martin Dyer, Alan Frieze and Ravi Kannan in 1988. The algorithm is based on a scheme for sampling nearly uniformly from within K. We motivate design of the algorithm and prove its correctness of it. The ideas used are mostly geometric and some basic theory of Markov Chain Monte Carlo methods. |