We study in this paper randomized algorithms to approximate the mixed volume of well-presented convex compact sets.
Our main result is a 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.\\
Our approach is ... more >>>

Convex relaxations based on different hierarchies of
linear/semi-definite programs have been used recently to devise
approximation algorithms for various optimization problems. The
approximation guarantee of these algorithms improves with the number
of {\em rounds} $r$ in the hierarchy, though the complexity of solving
(or even writing down the solution for) ... more >>>