LATTICE TRANSLATES OF A POLYTOPE AND THE FROBENIUS PROBLEM

This paper considers the "Frobenius problem": Given n natural numbers a1, a2.... a(n) such that their greatest common divisor is 1, find the largest natural number that is not expressible as a nonnegative integer combination of them. This problem can be seen to be NP-hard. For the cases n = 2,3 polynomial time algorithms are known to solve it. Here a polynomial time algorithm is given for every fixed n. This is done by first proving an exact relation between the Frobenius problem and a geometric concept called the "covering radius". Then a polynomial time algorithm is developed for finding the covering radius of any polytope in a fixed number of dimensions. The last algorithm relies on a structural theorem proved here that describes for any polytope K, the set K + Z(n) = {x : x is-an-element-of R(n) ; x = y + z ; y is-an-element-of K ; z is-an-element-of Z(n)} which is the portion of space covered by all lattice translates of K. The proof of the structural theorem relies on some recent developments in the Geometry of Numbers. In particular, it uses a theorem of Kannan and Lovasz [11], bounding the width of lattice-point-free convex bodies and the techniques of Kannan, Lovasz and Scarf [12) to study the shapes of a polyhedron obtained by translating each facet parallel to itself. The concepts involved are defined from first principles. In a companion paper [10], I extend the structural result and use that to solve a general problem of which the Frobenius problem is a special case.