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)

• Practical polytope volume approximation
• A practical volume algorithm
• Practical volume estimation of zonotopes by a new annealing schedule for cooling convex bodies
• Efficient sampling in spectrahedra and volume approximation
• Honey from the hives: a theoretical and computational exploration of combinatorial hives
• Convergence of Gibbs sampling: coordinate hit-and-run mixes fast
• VolEsti
• Computing mixed volume and all mixed cells in quermassintegral time
• 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
• Pruning algorithms for pretropisms of Newton polytopes
• Maximum entropy Gaussian approximations for the number of integer points and volumes of polytopes
• 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
• Sampling the feasible sets of SDPs and volume approximation
• Improved polytope volume calculations based on Hamiltonian Monte Carlo with boundary reflections and sweet arithmetics
• The diameter of the Birkhoff polytope

Describes a project that uses

Uses Software

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

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)