Name
Abstract | ||
|---|---|---|
We examine two different ways of encoding a counting function: as a rational generating function and explicitly as a function (defined piecewise using the greatest integer function). We prove that, if the degree and number of input variables of the (quasi-polynomial) function are fixed, there is a polynomial time algorithm which converts between the two representations. Examples of such counting functions include Ehrhart quasi-polynomials, vector partition functions, integer points in parametric polytopes, and projections of the integer points in parametric polytopes. For this last example, this algorithm provides the first known way to compute the explicit function in polynomial time. We rely heavily on results by Barvinok and Pommersheim [Barvinok, A., Pommersheim, J., 1999. An algorithmic theory of lattice points in polyhedra. In: New Perspectives in Algebraic Combinatorics (Berkeley, CA, 1996-97). In: Math. Sci. Res. Inst. Publ., vol. 38. Cambridge Univ. Press, Cambridge, pp. 91-147], and also by Verdoolaege et al. [Verdoolaege, S., Seghir, R., Beyls, K., Loechner, V., Bruynooghe, M., 2007. Counting integer points in parametric polytopes using Barvinok's rational functions, Algorithmica 48 (1), 37-66]. |
Year | DOI | Venue |
|---|---|---|
2008 | 10.1016/j.jsc.2007.07.007 | J. Symb. Comput. |
Keywords | DocType | Volume |
rational generating function,explicit function,rational generating functions,barvinok algorithm 2000 msc: 05a15,Cambridge Univ,counting function,parametric counting functions,Barvinok algorithm,integer point,vector partition functions,Piecewise quasi-polynomials,piecewise quasi-polynomials,Parametric polytopes,Parametric counting functions,vector partition function,greatest integer function,polynomial time,Vector partition functions,68w30,parametric polytopes,52b11,Rational generating functions,rational function | Journal | 43 |
Issue | ISSN | Citations |
2 | Journal of Symbolic Computation | 9 |
PageRank | References | Authors |
0.70 | 8 | 2 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sven Verdoolaege | 1 | 706 | 46.15 |
| Kevin Woods | 2 | 19 | 1.63 |