Zurück zu den Preprints des Jahres 2010


2010-32

LLL-reduction for Integer Knapsacks

by I. Aliev, M. Henk.


Series: 2010-32, Preprints

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

Abstract:
Given a matrix $A\in \Z^{m\times n}$ satisfying certain
regularity assumptions, a well-known integer programming problem asks to find an integer point in the associated {\em knapsack polytope}
$P(A,{\ve b})=\{{\ve x}\in \R^n_{\ge 0}: A {\ve x}={\ve b}\}$,
or determine that no such point exists.
We obtain a LLL-based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector ${\ve b}$.

Keywords:
Knapsack problem, Frobenius number, successive minima, inhomogeneous minimum, distribution of lattices