Approximations of Polytope Enumerators using Linear Expansions ∗

Several scientific problems are represented as sets of linear (or affine) con-straints over a set of variables and symbolic constants. When solutions of inter-est are integers, the number of such integer solutions is generally a meaningful information. Ehrhart polynomials are functions of the symbolic constants that count these solutions. Unfortunately, they have a complex mathematical struc-ture (resembling polynomials, hence the name), making it hard for other tools to manipulate them. Furthermore, their use may imply exponential computational complexity. This paper presents two contributions towards the useability of Ehrhart polynomials, by showing how to compute the following polynomial functions: an approximation and an upper (and a lower) bound of an Ehrhart polynomial. The computational complexity of this polynomial is less than or equal to that o