Efficient random-walk methods for approximating polytope volume

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

Authors: 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

Recommendations

• Practical polytope volume approximation
• Random walks in a convex body and an improved volume algorithm
• scientific article; zbMATH DE number 1149839
• Random walks and anO*(n5) volume algorithm for convex bodies
• A practical volume algorithm

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 (18)

• Practical polytope volume approximation
• Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
• A practical volume algorithm
• Honey from the hives: a theoretical and computational exploration of combinatorial hives
• 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
• Pruning algorithms for pretropisms of Newton polytopes
• Random walks in a convex body and an improved volume algorithm
• A random polynomial-time algorithm for approximating the volume of convex bodies
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• A Fast and Practical Method to Estimate Volumes of Convex Polytopes
• The diameter of the Birkhoff polytope
• Sampling the feasible sets of SDPs and volume approximation
• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics

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)