Efficient Random-Walk Methods for Approximating Polytope Volume

DOI10.1145/2582112.2582133zbMATH Open1395.68300arXiv1312.2873OpenAlexW2036015370WikidataQ57908671 ScholiaQ57908671MaRDI QIDQ4635556FDOQ4635556

Ioannis Z. Emiris, Vissarion Fisikopoulos

Publication date: 23 April 2018

Published in: Proceedings of the thirtieth annual symposium on Computational geometry (Search for Journal in Brave)

Abstract: We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear inequalities. We implement and evaluate practical randomized algorithms for accurately approximating the polytope's volume in high dimensions (e.g. one hundred). To carry out this efficiently we experimentally correlate the effect of parameters, such as random walk length and number of sample points, on accuracy and runtime. Moreover, we exploit the problem's geometry by implementing an iterative rounding procedure, computing partial generations of random points and designing fast polytope boundary oracles. Our publicly available code is significantly faster than exact computation and more accurate than existing approximation methods. We provide volume approximations for the Birkhoff polytopes B_11,...,B_15, whereas exact methods have only computed that of B_10.

Full work available at URL: https://arxiv.org/abs/1312.2873

zbMATH Keywords

random walksoftwarealgorithm engineeringgeneral dimensionpolytope oracleBirkhoff polytopesvolume approximation

Mathematics Subject Classification ID

Randomized algorithms (68W20) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Approximation algorithms (68W25) (n)-dimensional polytopes (52B11) Computational aspects related to convexity (52B55)

Cited In (13)

• Pruning Algorithms for Pretropisms of Newton Polytopes
• Honey from the Hives: A Theoretical and Computational Exploration of Combinatorial Hives
• A practical volume algorithm
• Efficient sampling in spectrahedra and volume approximation
• Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
• Computing mixed volume and all mixed cells in quermassintegral time
• A weighted belief-propagation algorithm for estimating volume-related properties of random polytopes
• VolEsti
• Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• A Fast and Practical Method to Estimate Volumes of Convex Polytopes
• The diameter of the Birkhoff polytope

Uses Software

• CGAL
• Matlab
• Boost C++ Libraries
• Eigen
• ANN
• FLANN
• Vinci

This page was built for publication: Efficient Random-Walk Methods for Approximating Polytope Volume

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4635556)