HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Journal articles

Efficient Random-Walk Methods for Approximating Polytope Volume

Ioannis Z. Emiris 1, 2 Vissarion Fisikopoulos 1
2 AROMATH - AlgebRe, geOmetrie, Modelisation et AlgoriTHmes
CRISAM - Inria Sophia Antipolis - Méditerranée , NKUA - National and Kapodistrian University of Athens
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 .
Complete list of metadata

Cited literature [37 references]  Display  Hide  Download

Contributor : Ioannis Emiris Connect in order to contact the contributor
Submitted on : Sunday, October 28, 2018 - 12:43:28 PM
Last modification on : Friday, February 4, 2022 - 3:18:45 AM
Long-term archiving on: : Tuesday, January 29, 2019 - 12:50:14 PM


Files produced by the author(s)




Ioannis Z. Emiris, Vissarion Fisikopoulos. Efficient Random-Walk Methods for Approximating Polytope Volume. ACM Transactions on Mathematical Software, Association for Computing Machinery, 2018, 44 (4), pp.1 - 21. ⟨10.1145/3194656⟩. ⟨hal-01897272⟩



Record views


Files downloads