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

ABSTRACT

We present a randomised polynomial time algorithm for approximating the volume of a convex body K in n-dimensional Euclidean space. 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.

REFERENCES

• 1: D.Aldous, Random walks on finite groups and rapidly missing Markov chains, S6minaire de Probabilite~ XVII, 1981-1982, Springer-Verlag Lecture Notes in Mathematics 986, pp. 243-297.
• 2: Z Furedi , I Barany, Computing the volume is difficult, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.442-447, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12176]
• 3: P. B6rard, G.Besson and A.S.Gallot, Sur une indgalitg isopdrimdtrique qui gdneralise ceUe de Paul Levy - Gromov, Inventiones Mathematicae 80 (1985)29~-aos.
• 4: A Z Broder, How hard is it to marry at random? (On the approximation of the permanent), Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.50-58, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12136]
• 5: M. E. Dyer , A. M. Frieze, On the complexity of computing the volume of a polyhedron, SIAM Journal on Computing, v.17 n.5, p.967-974, October 1988 [doi>10.1137/0217060]
• 6: G.Elekes, A geometric inequality and the complexity of computing volume, Discrete and Computational Geometry, Vol. 1, (1986) 289-292.
• 7: W.E.Feller, Introduction to probability theory and its applications, 3rd edition, Wiley, 1968.
• 8: D.Gilbarg and N.S.Trudinger, Elliptic partial differential equations of second order, ~7.2, Springer- Verlag, 1983.
• 9: M.GrStschel, L.Lov~sz and A.Schrijver, Geometric algoriihms and combinatorial optimization, Springer- Verlag (1988)
• 10: W.Hoeffding, Probability inequalities for sums of bounded random variables, Journal of the American Statistical Association 58 (1963) 13-30.
• 11: Mark Jerrum , Alistair Sinclair, Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.235-244, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62234]
• 12: M R Jerrum , L G Valiant , V V Vazirani, Random generation of combinatorial structures from a uniform, Theoretical Computer Science, v.43 n.2-3, p.169-188, July 1986
• 13: R.M.Karp and M.Luby, Monte Carlo algorithms for enumeration and reliability problems, Proceedings of the Twenty-Fourth IEEE Symposium on Foundations of Computer Science (1983) 56-64.
• 14: L.Lov~sz, An algorithmic theory of numbers graphs and convexity, CBMS-NSF Regional Conference Series on Applied Mathematics, Philadelphia, 1986.
• 15: Vitali D Milman , Gideon Schechtman, Asymptotic theory of finite dimensional normed spaces, Springer-Verlag New York, Inc., New York, NY, 1986
• 16: Alistair Sinclair , Mark Jerrum, Approximate counting, uniform generation and rapidly mixing Markov chains, Information and Computation, v.82 n.1, p.93-133, July 1989 [doi>10.1016/0890-5401(89)90067-9]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

General Terms:
Algorithms, Theory