{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,11]],"date-time":"2026-01-11T01:45:20Z","timestamp":1768095920615,"version":"3.49.0"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2018,6,16]],"date-time":"2018-06-16T00:00:00Z","timestamp":1529107200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"European Union's Horizon 2020 research and innovation programme","award":["734242 (LAMBDA)"],"award-info":[{"award-number":["734242 (LAMBDA)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Math. Softw."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>We experimentally study the fundamental problem of computing the volume of a convex polytope given as an intersection of linear halfspaces. We implement and evaluate randomized polynomial-time algorithms for accurately approximating the polytope\u2019s volume in high dimensions (e.g., few hundreds) based onhit-and-run random walks. To carry out this efficiently, we experimentally correlate the effect of parameters, such as random walk length and number of sample points, with accuracy and runtime. Our method is based on Monte Carlo algorithms with guaranteed speed and provably high probability of success for arbitrarily high precision. We exploit the problem\u2019s features in implementing a practical rounding procedure of polytopes, in computing only partial \u201cgenerations\u201d of random points, and in designing fast polytope boundary oracles. Our publicly available software is significantly faster than exact computation and more accurate than existing approximation methods. For illustration, volume approximations of Birkhoff polytopes<jats:italic>B<\/jats:italic><jats:sub>11<\/jats:sub>,\u2026,<jats:italic>B<\/jats:italic><jats:sub>15<\/jats:sub>are computed, in dimensions up to 196, whereas exact methods have only computed volumes of up to<jats:italic>B<\/jats:italic><jats:sub>10<\/jats:sub>.<\/jats:p>","DOI":"10.1145\/3194656","type":"journal-article","created":{"date-parts":[[2018,6,18]],"date-time":"2018-06-18T12:28:11Z","timestamp":1529324891000},"page":"1-21","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Practical Polytope Volume Approximation"],"prefix":"10.1145","volume":"44","author":[{"given":"Ioannis Z.","family":"Emiris","sequence":"first","affiliation":[{"name":"National and Kapodistrian University of Athens, Greece"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0780-666X","authenticated-orcid":false,"given":"Vissarion","family":"Fisikopoulos","sequence":"additional","affiliation":[{"name":"Universit\u00e9 libre de Bruxelles, Brussels, Belgium"}]}],"member":"320","published-online":{"date-parts":[[2018,6,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","unstructured":"P. K. Agarwal S. Har-Peled and K. R. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry. MSRI Berkeley 1--30. P. K. Agarwal S. Har-Peled and K. R. Varadarajan. 2005. Geometric approximation via coresets. In Combinatorial and Computational Geometry. MSRI Berkeley 1--30.","DOI":"10.1017\/9781009701259.002"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1327452.1327494"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261305"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-0348-8438-9_9"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187886"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/235815.235821"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.110"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-003-2850-8"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008733"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02573960"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00383444"},{"key":"e_1_2_1_12_1","unstructured":"W. Bruns B. Ichim and C. S\u00f6ger. 2013. Normaliz. Algorithms for rational cones and affine monoids. Retrieved from http:\/\/www.math.uos.de\/normaliz. W. Bruns B. Ichim and C. S\u00f6ger. 2013. Normaliz. Algorithms for rational cones and affine monoids. Retrieved from http:\/\/www.math.uos.de\/normaliz."},{"key":"e_1_2_1_13_1","unstructured":"B. B\u00fceler and A. Enge. 2000. VINCI. Retrieved from http:\/\/www.math.u-bordeaux1.fr\/ aenge\/index.php?category&equals;software8page&equals;vinci. B. B\u00fceler and A. Enge. 2000. VINCI. Retrieved from http:\/\/www.math.u-bordeaux1.fr\/ aenge\/index.php?category&equals;software8page&equals;vinci."},{"key":"e_1_2_1_14_1","volume-title":"Exact","volume":"29","author":"B\u00fceler B.","unstructured":"B. B\u00fceler , A. Enge , and K. Fukuda . 2000 . Exact Volume Computation for Polytopes: A Practical Study. Mathematics and Statistics, Vol. 29 . Birkh\u00e4user, Basel, 131--154. B. B\u00fceler, A. Enge, and K. Fukuda. 2000. Exact Volume Computation for Polytopes: A Practical Study. Mathematics and Statistics, Vol. 29. Birkh\u00e4user, Basel, 131--154."},{"key":"e_1_2_1_15_1","volume-title":"The asymptotic","author":"Canfield E.","year":"2009","unstructured":"E. Canfield and B. McKay . 2009. The asymptotic volume of the Birkhoff polytope. Online J. Anal. Comb. 4 ( 2009 ). E. Canfield and B. McKay. 2009. The asymptotic volume of the Birkhoff polytope. Online J. Anal. Comb. 4 (2009)."},{"key":"e_1_2_1_16_1","unstructured":"CGAL 2015. CGAL: Computational Geometry Algorithms Library. Retrieved from http:\/\/www.cgal.org. CGAL 2015. CGAL: Computational Geometry Algorithms Library. Retrieved from http:\/\/www.cgal.org."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1198\/016214504000001303"},{"key":"e_1_2_1_18_1","volume-title":"Proc. Symp. on Discrete Algorithms. SIAM\/ACM, 1215--1228","author":"Cousins B.","unstructured":"B. Cousins and S. Vempala . 2014. A cubic algorithm for computing gaussian volume . In Proc. Symp. on Discrete Algorithms. SIAM\/ACM, 1215--1228 . B. Cousins and S. Vempala. 2014. A cubic algorithm for computing gaussian volume. In Proc. Symp. on Discrete Algorithms. SIAM\/ACM, 1215--1228."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746563"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-015-0097-z"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00014-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2012.09.001"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10801-008-0155-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"crossref","unstructured":"P. Diaconis and B. Sturmfels. 1998. Algebraic algorithms for sampling from conditional distributions. Ann. Stat. 26 1 (02 1998) 363--397. P. Diaconis and B. Sturmfels. 1998. Algebraic algorithms for sampling from conditional distributions. Ann. Stat. 26 1 (02 1998) 363--397.","DOI":"10.1214\/aos\/1030563990"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217060"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102783"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199707)10:4%3C487::AID-RSA4%3E3.0.CO;2-Q"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187701"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/2582112.2582133"},{"key":"e_1_2_1_30_1","unstructured":"K. Fischer B. G\u00e4rtner T. Herrmann M. Hoffmann and S. Sch\u00f6nherr. 2013a. Bounding volumes. In CGAL User and Reference Manual (4.3 ed.). CGAL Editorial Board. Retrieved from http:\/\/doc.cgal.org\/4.3\/Manual\/packages.html#PkgBoundingVolumesSummary. K. Fischer B. G\u00e4rtner T. Herrmann M. Hoffmann and S. Sch\u00f6nherr. 2013a. Bounding volumes. In CGAL User and Reference Manual (4.3 ed.). CGAL Editorial Board. Retrieved from http:\/\/doc.cgal.org\/4.3\/Manual\/packages.html#PkgBoundingVolumesSummary."},{"key":"e_1_2_1_31_1","unstructured":"K. Fischer B. G\u00e4rtner S. Sch\u00f6nherr and F. Wessendorp. 2013b. Linear and quadratic programming solver. In CGAL User and Reference Manual (4.3 ed.). CGAL Editorial Board. http:\/\/doc.cgal.org\/4.3\/Manual\/packages.html#PkgQPSolverSummary. K. Fischer B. G\u00e4rtner S. Sch\u00f6nherr and F. Wessendorp. 2013b. Linear and quadratic programming solver. In CGAL User and Reference Manual (4.3 ed.). CGAL Editorial Board. http:\/\/doc.cgal.org\/4.3\/Manual\/packages.html#PkgQPSolverSummary."},{"key":"e_1_2_1_32_1","volume-title":"Algorithms and Combinatorics","volume":"2","author":"Gr\u00f6tschel M.","unstructured":"M. Gr\u00f6tschel , L. Lov\u00e1sz , and A. Schrijver . 1993. Geometric Algorithms and Combinatorial Optimization (2nd corrected ed.) . Algorithms and Combinatorics , Vol. 2 . Springer, Berlin. M. Gr\u00f6tschel, L. Lov\u00e1sz, and A. Schrijver. 1993. Geometric Algorithms and Combinatorial Optimization (2nd corrected ed.). Algorithms and Combinatorics, Vol. 2. Springer, Berlin."},{"key":"e_1_2_1_33_1","unstructured":"G. Guennebaud B. Jacob etal 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org. G. Guennebaud B. Jacob et al. 2010. Eigen v3. Retrieved from http:\/\/eigen.tuxfamily.org."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.procs.2011.04.151"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/261619.261620"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1110.0519"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258665"},{"key":"e_1_2_1_38_1","volume-title":"Complexity of polytope","author":"Khachiyan L.","unstructured":"L. Khachiyan . 1993. Complexity of polytope volume computation. In New Trends in Discrete and Computational Geometry. Springer, Berlin, 91-- 101 . L. Khachiyan. 1993. Complexity of polytope volume computation. In New Trends in Discrete and Computational Geometry. Springer, Berlin, 91--101."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.5555\/2871543.2871545"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1991-1079024-2"},{"key":"e_1_2_1_41_1","volume-title":"LNCS","volume":"4598","author":"Liu S.","unstructured":"S. Liu , J. Zhang , and B. Zhu . 2007. Volume computation using a direct Monte Carlo method. In Comp. and Combinatorics., G. Lin (Ed.) . LNCS , Vol. 4598 . Springer, Berlin, 198--209. S. Liu, J. Zhang, and B. Zhu. 2007. Volume computation using a direct Monte Carlo method. In Comp. and Combinatorics., G. Lin (Ed.). LNCS, Vol. 4598. Springer, Berlin, 198--209."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s101070050099"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2011.06.024"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970544727X"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2005.08.004"},{"key":"e_1_2_1_46_1","volume-title":"C++ Libraries","author":"Maurer J.","unstructured":"J. Maurer . 2000. Boost : C++ Libraries . Chapter 23. Boost Random. Retrieved from www.boost.org\/doc\/libs\/1_54_0\/doc\/html\/ boost_random.html. J. Maurer. 2000. Boost: C++ Libraries. Chapter 23. Boost Random. Retrieved from www.boost.org\/doc\/libs\/1_54_0\/doc\/html\/ boost_random.html."},{"key":"e_1_2_1_47_1","first-page":"1","article-title":"A parallel implementation of an O(n<sup>4<\/sup>) volume algorithm","volume":"3","author":"Moh\u00e1csi L.","year":"2015","unstructured":"L. Moh\u00e1csi and I. De\u00e1k . 2015 . A parallel implementation of an O(n<sup>4<\/sup>) volume algorithm . Cent. Eur. J. Op. Res. 3 , 24 (2015), 1 -- 28 . L. Moh\u00e1csi and I. De\u00e1k. 2015. A parallel implementation of an O(n<sup>4<\/sup>) volume algorithm. Cent. Eur. J. Op. Res. 3, 24 (2015), 1--28.","journal-title":"Cent. Eur. J. Op. Res."},{"key":"e_1_2_1_48_1","volume-title":"FLANN: Fast Library for Approximate Nearest Neighbors. Retrieved","author":"Muja M.","year":"2013","unstructured":"M. Muja . 2011. FLANN: Fast Library for Approximate Nearest Neighbors. Retrieved October 2013 from http:\/\/mloss.org\/software\/view\/143\/. M. Muja. 2011. FLANN: Fast Library for Approximate Nearest Neighbors. Retrieved October 2013 from http:\/\/mloss.org\/software\/view\/143\/."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/304893.304993"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1515\/form.2001.012"},{"key":"e_1_2_1_51_1","volume-title":"How to compute the","author":"Simonovits M.","unstructured":"M. Simonovits . 2003. How to compute the volume in high dimension? Math. Program. (2003), 337-- 374 . M. Simonovits. 2003. How to compute the volume in high dimension? Math. Program. (2003), 337--374."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.32.6.1296"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/2805882.2806038"},{"key":"e_1_2_1_54_1","first-page":"573","article-title":"Geometric random walks: A survey","volume":"52","author":"Vempala S.","year":"2005","unstructured":"S. Vempala . 2005 . Geometric random walks: A survey . Comb. Comput. Geom. 52 (2005), 573 -- 612 . S. Vempala. 2005. Geometric random walks: A survey. Comb. Comput. Geom. 52 (2005), 573--612.","journal-title":"Comb. Comput. Geom."},{"key":"e_1_2_1_55_1","volume-title":"Boost: C++ Libraries","author":"William A.","year":"2007","unstructured":"A. William and V. J. B. Escriba . 2007 . Boost: C++ Libraries . Chapter 32. Thread. Retrieved from http:\/\/www.boost.org\/doc\/libs\/1_56_0\/doc\/html\/thread.html. A. William and V. J. B. Escriba. 2007. Boost: C++ Libraries. Chapter 32. Thread. Retrieved from http:\/\/www.boost.org\/doc\/libs\/1_56_0\/doc\/html\/thread.html."},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1109\/TASE.2013.2272578"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3194656","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3194656","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,5]],"date-time":"2025-07-05T05:04:36Z","timestamp":1751691876000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3194656"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,6,16]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3194656"],"URL":"https:\/\/doi.org\/10.1145\/3194656","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,6,16]]},"assertion":[{"value":"2015-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2018-06-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}