08-18

Integer Knapsacks: Average behavior of the frobenius numbers

by Henk, M.; Aliev, I.

 

Preprint series: 08-18, Preprints

MSC:
11D04 Linear equations
11D85 Representation problems, See also {11P55}
68Q25 Analysis of algorithms and problem complexity

 

Abstract: Given a primitive integer vector $a\in \mathbb{Z}^N_{>0}$, the largest integer $b$ such that the knapsack polytope $P=\{x\in \mathbb{R}_{\geq 0}^N:\langle a,x\rangle=b\}$ contains no integer point is called the Frobenius number of $a$. We show that the asymptotic growth of the Frobenius number in average is significantly slower than the growth of the maximum Frobenius number. More precisely, we prove that it does not essentially exceed $\|a\|_{\infty}^{1+1/(N-1)}$, where $\|\cdot \|_{\infty}$ denotes the maximum norm.

Keywords: Frobenius number, successive minima, inhomogeneous minimum, distribution of sublattices


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: Webmaster