What is it about?

Polynomial-time methods and fast, open-source implementations for approximating the volume of convex polyhedra in high dimension, within any required precision. This is the first such software in C++ and continues to be state-of-the-art.

Featured Image

Why is it important?

Polytope volume is key in several convex optimization and related problems. Our methods introduce original uniform sampling techniques and geometric random walks.

Perspectives

Our methods lead to efficient ways for approximating the volume of any convex region, and have been used for estimating the volume of nonconvex regions as well. There is intense activity in this field and our state-of-the-art software offers important tools for experimentation and implementation of further algorithms. Since this article, our software library has been enhanced with new tools and methods.

Ioannis Emiris
National and Kapodistrian University of Athens

We wrote this article with my PhD thesis advisor while I was a PhD student. I am glad to see now that piece of software becoming an open-source library with a small but growing community and being the core that initiated new fascinating R&D projects. As far as I know the code of this article has been used by researchers to solve challenging problems in artificial intelligence and control.

Vissarion Fisikopoulos
National and Kapodistrian University of Athens

Read the Original

This page is a summary of: Practical Polytope Volume Approximation, ACM Transactions on Mathematical Software, December 2018, ACM (Association for Computing Machinery), DOI: 10.1145/3194656.
You can read the full text:

Read

Resources

Contributors

The following have contributed to this page