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

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.

## Citation

Los Alamos National Laboratory, 11/2006