Gröbner bases of lattices, corner polyhedra, and integer programming
Please always quote using this URN: urn:nbn:de:0297-zib-1548
- We investigate the generating sets (``Gröbner bases'') of integer lattices which correspond to the Gröbner bases of the associated binomial ideals. Extending results in Sturmfels and Thomas, preprint 1994, we obtain a geometric characterization of the universal Gröbner basis in terms of the vertices and edges of the associated corner polyhedra. We emphasize the special case where the lattice has finite index. In this case the corner polyhedra were studied by Gomory, and there is a close connection to the ``group problem in integer programming'' Schrijver, p.~363. We present exponential lower and upper bounds for the size of a reduced Gröbner basis. The initial complex of (the ideal of) a lattice is shown to be dual to the boundary of a certain simple polyhedron.
Author: | Bernd Sturmfels, Robert Weismantel, Günter M. Ziegler |
---|---|
Document Type: | ZIB-Report |
Date of first Publication: | 1994/10/17 |
Series (Serial Number): | ZIB-Report (SC-94-26) |
ZIB-Reportnumber: | SC-94-26 |
Published in: | Appeared in: Beiträge zur Algebra und Geometrie/Contributions to Algebra and Geometry 36 (1995) pp. 282-298 |