A Laplace transform algorithm for the volume of a convex polytope

Jean B. Lasserre (lasserrelaas.fr)
Eduardo S. Zeron (eszeronmath.cinvestav.mx)

Abstract: 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$.

Keywords: Convex polytope; volume; Laplace transform.

Category 1: Combinatorial Optimization (Polyhedra )

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

Download:

Entry Submitted: 12/06/2001
Entry Accepted: 12/06/2001
Entry Last Modified: 07/13/2002

Modify/Update this entry