10-32
LLL-reduction for Integer Knapsacks
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