10-32

LLL-reduction for Integer Knapsacks

by M. Henk I. Aliev

 

Preprint series: 10-32, 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, 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

Upload: 2011-01-18

Letzte Änderung: 01.03.2018 - Ansprechpartner: Webmaster