Shortest Integer Vectors
- 1 August 1993
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Mathematics of Operations Research
- Vol. 18 (3) , 516-522
- https://doi.org/10.1287/moor.18.3.516
Abstract
Let A be a fixed integer matrix of size m by n and consider all b for which the body Kb = {x: Ax ≤ b} is full dimensional. We examine the set of shortest nonzero integral vectors with respect to the family of norms whose unit balls are given by (Kb − Kb). We show that the number of such shortest vectors is polynomial in the bit size of A, for fixed n. We also show the existence, for any n, of a family of matrices M for which the number of shortest vectors has as a lower bound a polynomial in the bit size of M of the same degree as the polynomial bound.Keywords
All Related Versions
This publication has 0 references indexed in Scilit: