On the complexity of computing mixed volumes

Martin Dyer, Peter Gritzmann, Alexander Hufnagel

Research output: Contribution to journalArticlepeer-review

45 Scopus citations

Abstract

This 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 #ℙ-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is #ℙ-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 equation presented it of well-presented convex bodies K1, . . . , Ks, where m1, . . . , ms ∈ ℕ0 and m1 ≥ n - ψ(n) with ψ(n) = o(log n/log log n). The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies. This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research.

Original languageEnglish
Pages (from-to)356-400
Number of pages45
JournalSIAM Journal on Computing
Volume27
Issue number2
DOIs
StatePublished - 1998

Keywords

  • Approximation
  • Computation
  • Computational complexity
  • Computational convexity
  • Convex body
  • Deterministic algorithm
  • Mixed volumes
  • Parallelotope
  • Polynomial-time algorithm
  • Polytope
  • Randomized algorithm
  • Volume
  • Zonotope
  • ℕℙ-hardness

Fingerprint

Dive into the research topics of 'On the complexity of computing mixed volumes'. Together they form a unique fingerprint.

Cite this