Computational results of an O ∗( n 4) volume algorithm

► Computer implementation of a randomized algorithm for computing volumes. ► n-Dimensional Monte Carlo integration. ► Error analysis and variance reducing techniques. Recently an O ∗( n 4) volume algorithm has been presented for convex bodies by Lovász and Vempala, where n is the number of dimension...

Full description

Saved in:
Bibliographic Details
Published in:European journal of operational research 2012, Vol.216 (1), p.152-161
Main Authors: Lovász, L., Deák, I.
Format: Article
Language:English
Subjects:
Algorithms
Applied probability
Computational results
Estimating techniques
Markov processes
Monte Carlo computation
Monte Carlo simulation
Simulation
Studies
Volume algorithm
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:► Computer implementation of a randomized algorithm for computing volumes. ► n-Dimensional Monte Carlo integration. ► Error analysis and variance reducing techniques. Recently an O ∗( n 4) volume algorithm has been presented for convex bodies by Lovász and Vempala, where n is the number of dimensions of the convex body. Essentially the algorithm is a series of Monte Carlo integrations. In this paper we describe a computer implementation of the volume algorithm, where we improved the computational aspects of the original algorithm by adding variance decreasing modifications: a stratified sampling strategy, double point integration and orthonormalised estimators. Formulas and methodology were developed so that the errors in each phase of the algorithm can be controlled. Some computational results for convex bodies in dimensions ranging from 2 to 10 are presented as well.
ISSN:0377-2217
1872-6860
DOI:10.1016/j.ejor.2011.06.024