LLL-reduction for integer knapsacks |
| |
| Authors: | Iskander Aliev Martin Henk |
| |
| Institution: | 1. School of Mathematics and Wales Institute of Mathematical and Computational Sciences, Cardiff University, Senghennydd Road, Cardiff, Wales, UK
2. Fakult?t für Mathematik, Otto-von-Guericke Universit?t Magdeburg, Universit?tsplatz 2, 39106, Magdeburg, Germany
|
| |
| Abstract: | Given a matrix A∈? m×n satisfying certain regularity assumptions, a well-known integer programming problem asks to find an integer point in the associated knapsack polytope or determine that no such point exists. We obtain an LLL-based polynomial time algorithm that solves the problem subject to a constraint on the location of the vector b. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
