Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleGroebner bases of lattices, corner polyhedra and integer programming
Author(s) Bernd Sturmfels, Robert Weismantel, Günter M. Ziegler
TextSturmfels, B., Weismantel, R., and Ziegler, G.: `Grobner bases of lattices, corner polyhedra and integer programming', Beitraege zur Algebra und Geometrie 36 (1995), 281-298.
TypeTechnical Report, Misc
AbstractThere are very close connections between the arithmetic of integer lattices, algebraic properties of the associated ideals, and the geometry and the combinatorics of corresponding polyhedra. In this paper we investigate the generating sets ("Groebner bases") of integer lattices that correspond to the Groebner bases of the associated binomial ideals. Extending results by Sturmfels & Thomas, we obtain a geometric characterization of the universal Groebner basis in terms of the vertices and edges of the associated corner polyhedra. In the special case where the lattice has finite index, the corner polyhedra were studied by Gomory, and there is a close connection to the "group problem in integer programming." We present exponential lower and upper bounds for the maximal size of a reduced Groebner basis. The initial complex of (the ideal of) a lattice is
shown to be dual to the boundary of a certain simple polyhedron.
Pages281 - 298
Translation No
Refereed No