A Random Polynomial Time Algorithm for Approximating The Volume of Convex Bodies



Friday, 27 May 2016, 16:00 to 17:30


  • A-201 (STCS Seminar Room)


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.