A Laplace transform algorithm for the volume of a convex polytope

We provide two algorithms for computing the volume of the convex polytope $\Omega:=\{x\in \R^n_+ \,|\,Ax\leq b\}$, for $A\in\R^{m\times n}, b\in\R^n$. The computational complexity of both algorithms is essentially described by $n^m$, which makes them especially attractive for large $n$ and relatively small $m$, when the other methods with $O(m^n)$ complexity fail. The methodology which differs from previous existing methods uses a Laplace transform technique that is well suited to the half-space representation of $\Omega$.


J. of the ACM 48 (2001), 1126--1140.