A random polynomial-time algorithm for approximating the volume of convex bodies

1991/01/03 by Martin Dyer, Alan Frieze, Ravi Kannan · 7 citations
Mathematics · #Markov Chains and Monte Carlo Methods #Point processes and geometric inequalities #Stochastic processes and statistical mechanics

paper · pdf · doi:10.1145/102782.102783

openalex publication_date 1991/01/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/09

Abstract

A randomized polynomial-time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K .

Citations

• Sur une in�galit� isop�rim�trique qui g�n�ralise celle de Paul L�vy-Gromov
• Probability Inequalities for Sums of Bounded Random Variables

Cited by

• Polynomial-Time Approximation Algorithms for the Ising Model
• The Nature of Computation
• An Introduction to MCMC for Machine Learning
• Large Cliques Elude the Metropolis Process
• Extended studies of separability functions and probabilities and the relevance of Dyson indices
• Geometric Methods for Robust Data Analysis in High Dimension
• Algorithm [wikipedia]