shortest vector – Optimization Online

Basis Reduction, and the Complexity of Branch-and-Bound

Published: 2009/07/21, Updated: 2009/07/22

Combinatorial Optimization, Integer Programming basis reduction, Branch-and-Bound, integer programming, shortest vector

The classical branch-and-bound algorithm for the integer feasibility problem has exponential worst case complexity. We prove that it is surprisingly efficient on reformulations, in which the columns of the constraint matrix are short, and near orthogonal, i.e. a reduced basis of the generated lattice; when the entries of A (i.e. the dense part of the … Read more

On sublattice determinants in reduced bases

Published: 2008/04/24, Updated: 2022/05/13

Gabor Pataki

Mustafa Tural

Integer Programming, Other Topics basis reduction, geometry of numbers, shortest vector, subdeterminants

We prove several inequalities on the determinants of sublattices in LLL-reduced bases. They generalize the fundamental inequalities of Lenstra, Lenstra, and Lovasz on the length of the shortest vector, and show that LLL-reduction finds not only a short vector, but also sublattices with small determinants. We also prove new inequalities on the product of the … Read more