A quick estimate for the volume of a polyhedron

Abstract

Let $P$ be a bounded polyhedron defined as the intersection of the non-negative orthant ${\mathbb{R}}_{+}^n$ and an affine subspace of codimension $m$ in ${\mathbb{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.

23 pages, various improvements