A quick estimate for the volume of a polyhedron
A quick estimate for the volume of a polyhedron
复制标题
多面体体积的快速估计
DOI：
--
复制
发表时间：
2021
影响因子：
1
通讯作者：
M. Rudelson
中科院分区：
文献类型：
--
作者：
A. Barvinok;M. Rudelson
设P是一个有界多面体，它定义为非负正交子空间与余维为m的仿射子空间的交。我们表明，一个简单的和计算效率的公式近似的体积$P$内的一个因素$\gamma^m$，其中$\gamma>0$是一个绝对常数。该公式提供了最知名的估计运输多面体的体积从一个广泛的家庭。
Let $P$ be a bounded polyhedron defined as the intersection of the non-negative orthant ${\Bbb R}^n_+$ and an affine subspace of codimension $m$ in ${\Bbb R}^n$. We show that a simple and computationally efficient formula approximates the volume of $P$ within a factor of $\gamma^m$, where $\gamma>0$ is an absolute constant. The formula provides the best known estimate for the volume of transportation polytopes from a wide family.