A quick estimate for the volume of a polyhedron

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 $γ^m$, where $γ>0$ is an absolute constant. The formula provides the best known estimate for the volume of transportation polytopes from a wide family.

No reviews yet.

No comments yet.