Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)

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.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
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
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.