I was wondering if anybody had any pointers to:
1. References for the problem of vertex counting on convex polytopes
2. Possible implementations of known algorithms for such problem
So far I found:
- cdd (by Komei Fukuda)
- lrs (by David Avis)
- azove (by Markus Behle)
The references to the corresponding methods can be found on the authors websites and the corresponding documentation.
The first two focus more on vertex enumeration and not just counting, while the third one focuses on the problem of counting 0/1 vertices on polytopes with coefficients in $\mathbb{Z}$.
A second question motivated by the last method:
Assuming that it's possible, are there any known methods for computing a combinatorially isomorphic polytope $A$ with coefficients in $\mathbb{R}$ from a polytope $A$ with coefficients in $\mathbb{Z}$?
Update: The answer to this last question seems to be no (see Tsuyoshi Ito's comment below)
A third related question:
Not sure if the answer to the previous question answers this one, but are there any known transformations that preserve vertex cardinality from polytopes with coefficients in $\mathbb{R}$ to polytopes with coefficients in $\mathbb{Z}$?
#P-hard
, but did not know it extended to the 0/1 case as well. I guess what I am wondering if there are any other state-of-the-art methods besides those I listed, and if there has been any progress on this matter, maybe along the lines of PTAS or PRAS $\endgroup$ – Amelio Vazquez-Reina Sep 7 '11 at 21:28