This Article Full Text (PDF) References Alert me when this article is cited Alert me if a correction is posted Services Email this article to a friend Similar articles in this journal Alert me to new issues of the journal Download to citation manager Google Scholar Articles by Aliev, I. Articles by Henk, M.

Integer Knapsacks: Average Behavior of the Frobenius Numbers

School of Mathematics and Wales Institute of Mathematical and Computational Sciences, Cardiff University, Cardiff, Wales, CF24 4AG United Kingdom
Institut für Algebra und Geometrie, Otto-von-Guericke Universität Magdeburg, D-39106 Magdeburg, Germany
alievi{at}cf.ac.uk
henk{at}math.uni-magdeburg.de

The largest integer that cannot be represented as a nonnegative integral combination of given set of positive integers is called the Frobenius number of these integers. We show that the asymptotic growth of the Frobenius number on average is significantly slower than the growth of the maximum Frobenius number.

Key Words: knapsack problem; Frobenius number; successive minima; inhomogeneous minimum; distribution of lattices
History: Received: October 2, 2008; revision received: February 24, 2009;