Efficient random-walk methods for approximating polytope volume

DOI10.1145/2582112.2582133MaRDI QIDQ4635556zbMATH OpenOpenAlexWikidataFDO

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)

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)

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.

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

Cited in

(18)

• Efficient sampling in spectrahedra and volume approximation
• Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
• A weighted belief-propagation algorithm for estimating volume-related properties of random polytopes
• Gaussian Cooling and $O^*(n^3)$ Algorithms for Volume and Gaussian Volume
• The diameter of the Birkhoff polytope
• Sampling the feasible sets of SDPs and volume approximation
• A Fast and Practical Method to Estimate Volumes of Convex Polytopes
• Computing mixed volume and all mixed cells in quermassintegral time
• Practical polytope volume approximation
• Random walks in a convex body and an improved volume algorithm
• Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics
• Honey from the hives: a theoretical and computational exploration of combinatorial hives
• A random polynomial-time algorithm for approximating the volume of convex bodies
• VolEsti
• Pruning algorithms for pretropisms of Newton polytopes
• A practical volume algorithm
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes

Describes a project that uses

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)