Information-Theoretic Aspects of Integer-Point Enumeration in Polyhedra, Date: 2008/07/01 - 2008/07/01, Location: Las Vegas, Nevada
The 2008 International Conference on Information Theory and Statistical Learning
Author:
Keywords:
integer hulls, integer projections, parametric polytopes, partitioning lemma, rational generating functions
Abstract:
We describe the first implementation of the Barvinok--Woods (2003) algorithm, which computes a short rational generating function for an integer projection of the set of integer points in a polytope in polynomial time, when the dimension is fixed. The algorithm is based on Kannan's partitioning lemma and the application of set operations to generating functions that correspond to these sets. We use a variant of the recent strengthening of the partitioning lemma due to Eisenbrand and Shmonin (2007) and provide several algorithmic refinements to avoid performing redundant set operations. The implementation has been done in the second author's library.