A practical volume algorithm

  • We present a practical algorithm for computing the volume of a convex body with a target relative accuracy parameter ?>0. The convex body is given as the intersection of an explicit set of linear inequalities and an ellipsoid. The algorithm is inspired by the volume algorithms in Lovász and Vempala (J Comput Syst Sci 72(2):392–417, 2006) and Cousins and Vempala (SODA, pp. 1215–1228, 2014), but makes significant departures to improve performance, including the use of empirical convergence tests, an adaptive annealing scheme and a new rounding algorithm. We propose a benchmark of test bodies and present a detailed evaluation of our algorithm. Our results indicate that that volume computation and integration might now be practical in moderately high dimension (a few hundred) on commodity hardware.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar
Metadaten
Author:Ben Cousins, Santosh Vempala
DOI:https://doi.org/10.1007/s12532-015-0097-z
ISSN:1867-2949
Parent Title (English):Mathematical Programming Computation
Publisher:Springer Science and Business Media LLC
Document Type:Article
Language:English
Year of Completion:2015
Tag:Software; Theoretical Computer Science
Volume:8
Issue:2
Page Number:28
First Page:133
Last Page:160
Mathematical Programming Computation :MPC 2016 - Issue 2
Verstanden ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.