Optimization Online


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

Leonid Gurvits (gurvits***at***lanl.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

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society