- 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/2007Entry Accepted: 02/02/2007Entry Last Modified: 04/11/2007Modify/Update this entry Visitors Authors More about us Links Subscribe, Unsubscribe Digest Archive Search, Browse the Repository Submit Update Policies Coordinator's Board Classification Scheme Credits Give us feedback Optimization Journals, Sites, Societies Optimization Online is supported by the Mathematical Programming Society and by the Optimization Technology Center.