Practical Polytope Volume Approximation
Practical Polytope Volume Approximation
复制标题
DOI：
10.1145/3194656
复制
发表时间：
2018-08-01
影响因子：
2.7
通讯作者：
Fisikopoulos, Vissarion
中科院分区：
文献类型：
--
作者：
Emiris, Ioannis Z.;Fisikopoulos, Vissarion
我们的实验研究的基本问题计算的凸多面体的体积作为一个线性半空间的交集。我们实现和评估随机多项式时间算法，用于精确地近似高维多面体的体积（例如，几百个）基于打了就跑的随机游走。为了有效地实现这一点，我们通过实验将参数的影响（如随机游走长度和样本点数量）与准确性和运行时间相关联。我们的方法是基于蒙特卡洛算法，保证速度和可证明的高概率成功的任意高精度。我们利用这个问题的特点，在实现一个实用的圆形程序的多面体，在计算只有部分“代”的随机点，并在设计快速多面体边界预言。我们的公开软件比精确计算快得多，比现有的近似方法更准确。为了说明，Birkhoff多面体B-11，.，B-15的计算，在尺寸高达196，而精确的方法只计算体积高达B-10。
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's volume in high dimensions (e.g., few hundreds) based onhit-andrun 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's features in implementing a practical rounding procedure of polytopes, in computing only partial "generations" 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 B-11,..., B-15 are computed, in dimensions up to 196, whereas exact methods have only computed volumes of up to B-10.