Zurück zu den Preprints des Jahres 2009


2009-42

On feasibility of integer knapsacks

by Aliev, I., Henk, M..


Series: 2009-42, Preprints

MSC:
90C10 Integer programming
90C27 Combinatorial optimization
11H06 Lattices and convex bodies

Abstract:
Given a matrix A 2 Zm×n satisfying certain regularity as-
sumptions, we consider the set F(A) of all vectors b 2 Zm such that the associated knapsack polytope
P(A, b) = {x 2 Rn0 : Ax = b} contains an integer point. When m = 1 the set F(A) is known to contain all consecutive integers greater than the Frobenius number associated
with A. In this paper we introduce the diagonal Frobenius number g(A) which reflects in an analogous way feasibility properties of the problem and the structure of F(A) in the general case. We give an optimal upper bound for g(A) and also estimate the asymptotic growth of the diagonal
Frobenius number on average.

Keywords:
Knapsack problem; Frobenius numbers; successive minima; inhomogeneous minimum; distribution of lattices