article

Free access

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

Authors:

Martin Dyer,

Alan Frieze,

Ravi KannanAuthors Info & Claims

Journal of the ACM (JACM), Volume 38, Issue 1

Pages 1 - 17

https://doi.org/10.1145/102782.102783

Published: 03 January 1991 Publication History

PDF eReader

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,

Google Scholar

[2]

~BARANY, I., AND FUREDI, Z. Computing the volume is difficult. In Proceed~t~gs of the 18th Annual ~AC,5! S l't>lposlum on Theory of Compttllng (Berkeley, Calif., May 28-30). ACM, New York, 1986, ~ pp. 442-447.

Digital Library

Google Scholar

[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.

Google Scholar

[4]

~BRODER, A. Z' How hard is it to marry at random? (On the approximation of the permanent). In ~Proceedlngs' of the 18{h Attmtal ACM Sj'tHpOXltttt,1 otl zhe Theory' of Computzng (Berkeley, Calif., ~May 28-30). ACM, New York, 1986, pp. 50-58.

Digital Library

Google Scholar

[5]

~DYER, M E., AND FRIEZE, h.M. On the complexity of computing the volume of a polyhedron. ~S1AMJ Com?ut 17, 5 (Oct. 1988), 967-975.

Digital Library

Google Scholar

[6]

~ELEKES, G. A geometric inequahty and the complexity of computing volume. Dtscr Comput ~Geom 1 (1986), 289-292.

Google Scholar

[7]

~FELLER, W E. Introdzwtton to Probabthty Theot3, atzd Its Apphcatzcms 3rd ed. Wil%, New York, ~1968.

Google Scholar

[8]

~GILBA. RG, D., AND TRUDINGER, N. S. Elll})llC Parttal DtlferetzHal Eqt~alzons o{'Second Order ~Sprmger-Verlag, New York, 1983, p. 147

Google Scholar

[9]

~GROTSCHEL, M., LOVASZ, L.,AND SCHRIJVER, A. Geometric Algor~thmy and Combinatorial ~Optlmtzat,m Springer-Verlag, New York, 1988

Google Scholar

[10]

~ HOEFFDING, W. Probability inequalities for sums of bounded random variables. J Am Slat ~ Assoc 58 (1963), 13-30.

Google Scholar

[11]

~JERRUM, M R., AND SINCLAIR, A. J Conductance and the rapid mixing property for Markov ~chains: The approximation of the permanent resolved. In Ptoceedttlg~ of the 20lh Annual ACM ~~l'rnpo3lttt~ cm the Theot3, o/' Compztttng (Chicago, II1., May 2-4). ACM, New York, 1988, ~pp. 235-244.

Digital Library

Google Scholar

[12]

~JERRUM, M. R., VAriANT, L. G., AND VAZIRANL V. V. Random generation of combinatorial ~structures from a uniform distribution. Theoret Cotnpzlt Sol 43 (1986), 169-188.

Digital Library

Google Scholar

[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.

Google Scholar

[14]

~Lov/~sz, L. An algorithmic theory of numbers graphs and convexity. CBMS-NSF Regional ~Conference Series on Applied Mathematics, Philadelphia, Pa., 1986.

Google Scholar

[15]

~MILMAN, V. D., AND SCHECTMANN, O. Asymptotic theory of finite d~mensional normed spaces. ~Lecture Notes in Mathematics', vol. 1200. Springer-Verlag, New York, 1980.

Digital Library

Google Scholar

[16]

~SINCLAIR, A. J., AND JERRUM, M. R. Approximate counting, uniform generation and rapidly ~mixing Markov chains. Inf Compttt. 82 (1989), 93-133.

Digital Library

Google Scholar

Cited By

View all

Chalkis ABachelard CFisikopoulos VTsigaridas E(2024)Randomized Control in Performance Analysis and Empirical Asset PricingSSRN Electronic Journal10.2139/ssrn.4744249Online publication date: 2024
https://doi.org/10.2139/ssrn.4744249
Naidu SVenkiteswaran G(2024)Optimal oversampling ratio in two-step simulationMonte Carlo Methods and Applications10.1515/mcma-2024-2011Online publication date: 3-Aug-2024
https://doi.org/10.1515/mcma-2024-2011
Díaz AMorris PPerarnau GSerra O(2024)Speeding up random walk mixing by starting from a uniform vertexElectronic Journal of Probability10.1214/24-EJP109129:noneOnline publication date: 1-Jan-2024
https://doi.org/10.1214/24-EJP1091
Show More Cited By

Index Terms

A random polynomial-time algorithm for approximating the volume of convex bodies
1. Mathematics of computing
  1. Probability and statistics
    1. Probabilistic algorithms
    2. Probabilistic reasoning algorithms
      1. Markov-chain Monte Carlo methods
      2. Sequential Monte Carlo methods
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

A random polynomial time algorithm for approximating the volume of convex bodies
STOC '89: Proceedings of the twenty-first annual ACM symposium on Theory of computing

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 ...
Random Approximation of Convex Bodies: Monotonicity of the Volumes of Random Tetrahedra

Choose uniform random points $$X_1, \dots , X_n$$X1,ź,Xn in a given convex set and let $${\text { conv}}[X_1, \dots , X_n]$$conv[X1,ź,Xn] be their convex hull. It is shown that in dimension three the expected volume of this convex hull is in general not ...
Pseudorandom generators from polarizing random walks
CCC '18: Proceedings of the 33rd Computational Complexity Conference

We propose a new framework for constructing pseudorandom generators for n-variate Boolean functions. It is based on two new notions. First, we introduce fractional pseudorandom generators, which are pseudorandom distributions taking values in [-1, 1]ⁿ. ...

Reviews

Reviewer: Patrick J. Ryan

The authors present an algorithm for approximating the volume of a compact convex set <__?__Pub Fmt italic>K<__?__Pub Fmt /italic> in R n . The problem is difficult. The time required for the algorithm is shown to be polynomial in the dimension <__?__Pub Fmt italic>n<__?__Pub Fmt /italic>, but success (within a prescribed tolerance) is guaranteed only with probability 3/4. Since analysis of the algorithm is quite technical, I present only a brief sketch <__?__Pub Caret> here. After suitable normalization, the set <__?__Pub Fmt italic>K<__?__Pub Fmt /italic> may be taken to contain the unit ball <__?__Pub Fmt italic>B<__?__Pub Fmt /italic> but lie within the concentric ball <__?__Pub Fmt italic>rB<__?__Pub Fmt /italic>, where r= n+1 n . A shell-like decomposition K=K k ?K k-1 ?&ldots;?K 1 ?K 0 =rB is used to express the volume of <__?__Pub Fmt italic>K<__?__Pub Fmt /italic> as a telescoping product of the ratios of volumes of successive members K i ,K i-1 of the sequence. The space is covered by a fixed grid of cubes, and each ratio is computed by a specified number of trials; each trial involves choosing a point at random from a randomly chosen cube, then checking membership in K i-1 and K i . For each trial, the cube chosen is the result of a random walk of a fixed length polynomial in <__?__Pub Fmt italic>n<__?__Pub Fmt /italic>. The authors use the ergodic property of Markov chains to argue that this method gives a nearly uniform distribution from which the cubes are sampled. The paper contains many illuminating remarks in addition to the technical description and analysis of the algorithm.

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 38, Issue 1

Jan. 1991

254 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/102782

Editor:
Daniel J. Rosenkrantz
State Univ. of New York at Albany, NY

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 January 1991

Published in JACM Volume 38, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

409
Total Citations
View Citations
2,655
Total Downloads

Downloads (Last 12 months)306
Downloads (Last 6 weeks)37

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Chalkis ABachelard CFisikopoulos VTsigaridas E(2024)Randomized Control in Performance Analysis and Empirical Asset PricingSSRN Electronic Journal10.2139/ssrn.4744249Online publication date: 2024
https://doi.org/10.2139/ssrn.4744249
Naidu SVenkiteswaran G(2024)Optimal oversampling ratio in two-step simulationMonte Carlo Methods and Applications10.1515/mcma-2024-2011Online publication date: 3-Aug-2024
https://doi.org/10.1515/mcma-2024-2011
Díaz AMorris PPerarnau GSerra O(2024)Speeding up random walk mixing by starting from a uniform vertexElectronic Journal of Probability10.1214/24-EJP109129:noneOnline publication date: 1-Jan-2024
https://doi.org/10.1214/24-EJP1091
Chan SPak IMohar BShinkar IO'Donnell R(2024)Equality Cases of the Alexandrov–Fenchel Inequality Are Not in the Polynomial HierarchyProceedings of the 56th Annual ACM Symposium on Theory of Computing10.1145/3618260.3649646(875-883)Online publication date: 10-Jun-2024
https://dl.acm.org/doi/10.1145/3618260.3649646
Spaeh FTsourakakis CChua TNgo CKa-Wei Lee RKumar RLauw H(2024)Markovletics: Methods and A Novel Application for Learning Continuous-Time Markov Chain MixturesProceedings of the ACM Web Conference 202410.1145/3589334.3645491(4160-4171)Online publication date: 13-May-2024
https://dl.acm.org/doi/10.1145/3589334.3645491
Podgorelec VFister IVrbančič G(2024)Towards Green AI by Reducing Training Effort of Recurrent Neural Networks Using Hyper-Parameter Optimization with Dynamic Stopping Criteria2024 IEEE 22nd Jubilee International Symposium on Intelligent Systems and Informatics (SISY)10.1109/SISY62279.2024.10737555(000161-000166)Online publication date: 19-Sep-2024
https://doi.org/10.1109/SISY62279.2024.10737555
Peleg MShamai S(2024)Geometrical Bounds on the Capacity of the Binary Bipolar Input AWGN Channel2024 IEEE International Conference on Microwaves, Communications, Antennas, Biomedical Engineering and Electronic Systems (COMCAS)10.1109/COMCAS58210.2024.10666258(1-6)Online publication date: 9-Jul-2024
https://doi.org/10.1109/COMCAS58210.2024.10666258
Saavedra-Nieves ASaavedra-Nieves P(2024)On the estimation of the core for TU gamesExpert Systems with Applications10.1016/j.eswa.2023.123132245(123132)Online publication date: Jul-2024
https://doi.org/10.1016/j.eswa.2023.123132
Coronado TPons JRiera G(2024)Counting Cherry Reduction Sequences in Phylogenetic Tree-Child Networks is Counting Linear ExtensionsBulletin of Mathematical Biology10.1007/s11538-024-01374-186:12Online publication date: 9-Nov-2024
https://doi.org/10.1007/s11538-024-01374-1
Dadush DEisenbrand FRothvoss T(2024)From approximate to exact integer programmingMathematical Programming10.1007/s10107-024-02084-1Online publication date: 24-Apr-2024
https://doi.org/10.1007/s10107-024-02084-1
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations