Tata Institute of Fundamental Research
A Random Polynomial Time Algorithm for Approximating The Volume of Convex Bodies
STCS Student Seminar
Speaker:
Varun Narayanan
Organiser:
Nikhil S Mande
Date:
Friday, 27 May 2016, 16:00 to 17:30
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
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.
| Speaker: | Varun Narayanan |
| Organiser: | Nikhil S Mande |
| Date: | Friday, 27 May 2016, 16:00 to 17:30 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
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.