On the complexity of computing mixed volumes

The paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension. On the negative side we present several P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonoetopes is P-hard (while each corresponding mixed volume can be computed easily), but also give examples showing that computing mixed volumes is hard even when computing the volume is easy. On the positive side we derive a randomized algorithm for computing the mixed volumes of well-presented convex bodies. The algorithm is an interpolation method based on polynominal-time randomized algorithms for computing the volume of convex bodies. The paper concludes with applications of our results to various other problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers and operations research. (orig.)SIGLEAvailable from TIB Hannover: RO 7722(527) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekDEGerman