On the Frobenius Problem and its Generalization
Let N > 1 be an integer, and let 1 < a_1 < ... < a_N be relatively prime integers. Frobenius number of this N-tuple is defined to be the largest positive integer that cannot be represented as a linear combination of a_1,...,a_N with non-negative integer coefficients. More generally, the s-Frobenius number is defined to be the largest positive integer that has precisely s distinct representations like this, so that the classical Frobenius number can be thought of as the 0-Frobenius number. The condition that a_1,...,a_N are relatively prime implies that s-Frobenius numbers exist for every non-negative integer s. The general problem of determining the Frobenius number given N and a_1,...,a_N is known to be NP-hard, but there has been a number of different bounds on the Frobenius number produced by various authors. We use techniques from the Geometry of Numbers to produce an upper bound on the Frobenius number in terms of the covering radius of the null-lattice of the linear form with coefficients a_1,...,a_N. More generally, we are able to obtain upper and lower bounds on the s-Frobenius number for any nonnegative integer s. In this talk, we will discuss these and some related results on the Frobenius problem and its generalizations, as time allows.
© 2010 Lenny Fukshansky
Fukshansky, Lenny. "On the Frobenius Problem and its Generalization." Colloquium, University of Rostock, Rostock, Germany. 3 November 2010.