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

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.

REFERENCES

• 1: ~ALDOUS, D. Random walks on fimte groups and rapidly mixing Markov chains. In Sbmlnalre de ~Probablllt&,~{'7I, 198}-1982 Lecture Notes in Mathematics, vol. 986. Springer-Verlag, New York, ~1983, 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: ~BERARD, P., BESSON, G., AND GAELOT, A.S. Sur une m6galit6 isop6nm6trique qul g~nerahse celle ~de Paul Levy-Gromov. hzventzones Math 80 (1985), 295-308.
• 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: ~ELEKES, G. A geometric inequahty and the complexity of computing volume. Dtscr Comput ~Geom 1 (1986), 289-292.
• 7: ~FELLER, W E. Introdzwtton to Probabthty Theot3, atzd Its Apphcatzcms 3rd ed. Wil%, New York, ~1968.
• 8: ~GILBA. RG, D., AND TRUDINGER, N. S. Elll})llC Parttal DtlferetzHal Eqt~alzons o{'Second Order ~Sprmger-Verlag, New York, 1983, p. 147
• 9: ~GROTSCHEL, M., LOVASZ, L.,AND SCHRIJVER, A. Geometric Algor~thmy and Combinatorial ~Optlmtzat,m Springer-Verlag, New York, 1988
• 10: ~ HOEFFDING, W. Probability inequalities for sums of bounded random variables. J Am Slat ~ Assoc 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: ~KARP, R. M., AND LUBY, M. Monte Carlo algorithms for enumeratmn and reliability problems. ~In Proceedings oJ' the 24th IEEE Srrnposlum on FotmdaHons oj Computer &'zetwe IEEE, ~New York, 1983. pp. 56-64.
• 14: ~Lov/~sz, L. An algorithmic theory of numbers graphs and convexity. CBMS-NSF Regional ~Conference Series on Applied Mathematics, Philadelphia, Pa., 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory

Keywords:
convex sets, random walks, sampling, volume