Feasibility of integer knapsacks. (English) Zbl 1211.90132
Summary: Given a matrix \(A\in\mathbb{Z}^{m\times n}\) satisfying certain regularity assumptions, we consider the set \(\mathcal{F}(A)\) of all vectors \(b\in\mathbb{Z}^m\) such that the associated knapsack polytope \(P(A,b)=\{ x\in\mathbb{R}^n_{\geq0}:Ax=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 diagonal Frobenius number g\((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 g\((A)\) and also estimate the asymptotic growth of the diagonal Frobenius number on average.
MSC:
90C10 | Integer programming |
90C27 | Combinatorial optimization |
11D07 | The Frobenius problem |
11H06 | Lattices and convex bodies (number-theoretic aspects) |