09-42
On feasibility of integer knapsacks
Preprint series: 09-42, Preprints
- MSC:
- 90C10 Integer programming
- 90C27 Combinatorial optimization
- 11H06 Lattices and convex bodies, See also {11P21, 52C05, 52C07}
Abstract: Given a matrix $A\in \Z^{m\times n}$ satisfying certain regularity assumptions, we consider the set ${\mathcal F}(A)$ of all vectors ${\ve b}\in \Z^m$ such that the associated {\em knapsack polytope} P(A,{\ve b})=\{{\ve x}\in \R^n_{\ge 0}: A {\ve x}={\ve b}\}\, contains an integer point. When $m=1$ the set ${\mathcal F}(A)$ is known to contain all consecutive integers greater than the Frobenius number associated with $A$. In this paper we introduce the {\em diagonal Frobenius number} $\dfrob(A)$ which reflects in an analogous way feasibility properties of the problem and the structure of ${\mathcal F}(A)$ in the general case. We give an optimal upper bound for $\dfrob(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
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.