Skip to main content

Kevin M. Woods Publications

Publish Date
Abstract

Given a1, a2,…,an in Zd, we examine the set, G, of all nonnegative integer combinations of these ai. In particular, we examine the generating function f(z) = Sum{b in G}zb. We prove that one can write this generating function as a rational function using the neighborhood complex (sometimes called the complex of maximal lattice-free bodies or the Scarf complex) on a particular lattice in Zn. In the generic case, this follows from algebraic results of D. Bayer and B. Sturmfels. Here we prove it geometrically in all cases, and we examine a generalization involving the neighborhood complex on an arbitrary lattice.

Keywords: Integer programming, Complex of maximal lattice free bodies, Generating functions

JEL Classification: C61