ON THE COMPLEXITY OF COMPUTING MIXED VOLUMES

This paper gives various (positive and negative) results on the comple xity of the problem of computing and approximating mixed volumes of po lytopes and more general convex bodies in arbitrary dimension. On the negative side, we present several # P-hardness results that focus on t he difference of computing mixed volumes versus computing the volume o f polytopes. We show that computing the volume of zonotopes is # P-har d (while each corresponding mixed volume can be computed easily) but a lso give examples showing that computing mixed volumes is hard even wh en computing the volume is easy. On the positive side, we derive a ran domized algorithm for computing the mixed volumes [GRAPHICS] of well-p resented convex bodies K-1,...,K-s, where m(1),...,m(s) is an element of N-0 and m(1) greater than or equal to n - psi(n) with psi(n) = o(lo g n/log log n). The algorithm is an interpolation method based on poly nomial-time randomized log algorithms for computing the volume of conv ex bodies. This paper concludes with applications of our results to va rious problems in discrete mathematics, combinatorics, computational c onvexity, algebraic geometry, geometry of numbers, and operations rese arch.