Geodesic
Short rational generating functions for lattice point problems
Barvinok, Alexander1 ; Woods, Kevin1
1 Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109
Journal of the American Mathematical Society, Tome 16 (2003) no. 4, pp. 957-979

Voir la notice de l'article provenant de la source American Mathematical Society

We prove that for any fixed $d$ the generating function of the projection of the set of integer points in a rational $d$-dimensional polytope can be computed in polynomial time. As a corollary, we deduce that various interesting sets of lattice points, notably integer semigroups and (minimal) Hilbert bases of rational cones, have short rational generating functions provided certain parameters (the dimension and the number of generators) are fixed. It follows then that many computational problems for such sets (for example, finding the number of positive integers not representable as a non-negative integer combination of given coprime positive integers $a_{1}, \ldots , a_{d}$) admit polynomial time algorithms. We also discuss a related problem of computing the Hilbert series of a ring generated by monomials.
DOI : 10.1090/S0894-0347-03-00428-4

Barvinok, Alexander 1 ; Woods, Kevin 1

1 Department of Mathematics, University of Michigan, Ann Arbor, Michigan 48109-1109 
@article{10_1090_S0894_0347_03_00428_4,
     author = {Barvinok, Alexander and Woods, Kevin},
     title = {Short rational generating functions for lattice point problems},
     journal = {Journal of the American Mathematical Society},
     pages = {957--979},
     publisher = {mathdoc},
     volume = {16},
     number = {4},
     year = {2003},
     doi = {10.1090/S0894-0347-03-00428-4},
     url = {http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-03-00428-4/}
}
TY  - JOUR
AU  - Barvinok, Alexander
AU  - Woods, Kevin
TI  - Short rational generating functions for lattice point problems
JO  - Journal of the American Mathematical Society
PY  - 2003
SP  - 957
EP  - 979
VL  - 16
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-03-00428-4/
DO  - 10.1090/S0894-0347-03-00428-4
ID  - 10_1090_S0894_0347_03_00428_4
ER  - 
%0 Journal Article
%A Barvinok, Alexander
%A Woods, Kevin
%T Short rational generating functions for lattice point problems
%J Journal of the American Mathematical Society
%D 2003
%P 957-979
%V 16
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.1090/S0894-0347-03-00428-4/
%R 10.1090/S0894-0347-03-00428-4
%F 10_1090_S0894_0347_03_00428_4
Barvinok, Alexander; Woods, Kevin. Short rational generating functions for lattice point problems. Journal of the American Mathematical Society, Tome 16 (2003) no. 4, pp. 957-979. doi: 10.1090/S0894-0347-03-00428-4

[1] Barvinok, Alexander I. A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed Math. Oper. Res. 1994 769 779

[2] Barvinok, Alexander, Pommersheim, James E. An algorithmic theory of lattice points in polyhedra 1999 91 147

[3] Bayer, Dave, Sturmfels, Bernd Cellular resolutions of monomial modules J. Reine Angew. Math. 1998 123 140

[4] Banaszczyk, Wojciech, Litvak, Alexander E., Pajor, Alain, Szarek, Stanislaw J. The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces Math. Oper. Res. 1999 728 750

[5] Cassels, J. W. S. An introduction to the geometry of numbers 1997

[6] Eisenbud, David Commutative algebra 1995

[7] Erdå‘S, P., Graham, R. L. On a linear diophantine problem of Frobenius Acta Arith. 1972 399 408

[8] Grã¶Tschel, Martin, Lovã¡Sz, Lã¡Szlã³, Schrijver, Alexander Geometric algorithms and combinatorial optimization 1993

[9] Herzog, Jã¼Rgen Generators and relations of abelian semigroups and semigroup rings Manuscripta Math. 1970 175 193

[10] Kannan, Ravi Lattice translates of a polytope and the Frobenius problem Combinatorica 1992 161 177

[11] Khovanskiä­, A. G. Sums of finite sets, orbits of commutative semigroups and Hilbert functions Funktsional. Anal. i Prilozhen. 1995

[12] Kannan, Ravi, Lovã¡Sz, Lã¡Szlã³, Scarf, Herbert E. The shapes of polyhedra Math. Oper. Res. 1990 364 380

[13] Papadimitriou, Christos H. Computational complexity 1994

[14] Scarf, Herbert E. Test sets for integer programs Math. Programming 1997 355 368

[15] Schrijver, Alexander Theory of linear and integer programming 1986

[16] Sturmfels, Bernd Gröbner bases and convex polytopes 1996

[17] Szã©Kely, L. A., Wormald, N. C. Generating functions for the Frobenius problem with 2 and 3 generators Math. Chronicle 1986 49 57

[18] Thomas, Rekha R. A geometric Buchberger algorithm for integer programming Math. Oper. Res. 1995 864 884

Cité par Sources :