Polynomial time algorithms to approximate mixed volumes within a simply exponential factor

Leonid Gurvits (gurvitslanl.gov)

Abstract: We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets. Our main result is a randomized poly-time algorithm which approximates $V(K_1,...,K_n)$ with multiplicative error $e^n$ and with better rates if the affine dimensions of most of the sets $K_i$ are small.\\ Even such rate is impossible to achieve by a deterministic oracle algorithm. Our approach is based on the particular convex relaxation of $\log(V(K_1,...,K_n))$ via the geometric programming. We prove the mixed volume analogues of the Van der Waerden and the Schrijver/Valiant conjectures on the permanent. These results , interesting on their own, allow to "justify" the above mentioned convex relaxation, which is solved using the ellipsoid method and a randomized poly-time time algorithm for the approximation of the volume of a convex set.

Keywords: Convex sets, mixed volume, geometric programming, hyperbolic polynomial

Category 1: Combinatorial Optimization (Approximation Algorithms )

Category 2: Convex and Nonsmooth Optimization (Convex Optimization )

Citation: Los Alamos National Laboratory, 11/2006

Download: [PDF]

Entry Submitted: 02/01/2007
Entry Accepted: 02/02/2007
Entry Last Modified: 04/11/2007

Modify/Update this entry