On feasibility of integer knapsacks

by Aliev, I.; Henk, M.


Preprint series: 09-42, Preprints

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.

Letzte Änderung: 01.03.2018 - Ansprechpartner:

Sie können eine Nachricht versenden an: Webmaster