Exposition of an approximation algorithm for mixed volumes of a constant number of convex bodies
In the authors' words
We study -relative approximation of mixed volumes of a fixed number of full-dimensional convex bodies in , given membership oracles and a known bound . We present a randomized algorithm that estimates any prescribed mixed volume within relative error with probability at least , using polynomially many oracle calls and bit operations in , , , and for fixed .
Main resultLimitation the authors admit
Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 27 pages