pipette
ESEspañol

Exposition of an approximation algorithm for mixed volumes of a constant number of convex bodies

Hariharan Narayanan

Preprint

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