### 2010-32

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