ITEM METADATA RECORD
Title: An implementation of the Barvinok--Woods integer projection algorithm
Authors: Koeppe, Matthias ×
Verdoolaege, Sven
Woods, Kevin M. #
Issue Date: Jul-2008
Host Document: The 2008 International Conference on Information Theory and Statistical Learning pages:53-59
Conference: Information-Theoretic Aspects of Integer-Point Enumeration in Polyhedra location:Las Vegas, Nevada date:July 2008
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.
Publication status: published
KU Leuven publication type: IC
Appears in Collections:Informatics Section
× corresponding author
# (joint) last author

Files in This Item:
File Description Status SizeFormat
ITS6310.pdf Published 180KbAdobe PDFView/Open

 


All items in Lirias are protected by copyright, with all rights reserved.