Solving Subset Sum Problems with the \(L^3\) Algorithm

Ideas are described that speed up the lattice basis reduction algorithm of Lenstra, Lenstra, and Lovász \([11]\) in practice. The resulting lattice basis reduction algorithm reduces the multiprecision operations needed in previous approaches. This paper describes these ideas in detail for lattices of the particular form arising from the subset sum (exact knapsack) problem. The idea of applying the \(L^3\) algorithm to the subset sum problem is due to Lagarias and Odlyzko \([8]\). The algorithm of this paper also uses a direct search for short vectors simultaneously with the basis reduction algorithm. Extensive computational tests show that this algorithm solves, with high probability, instances of low-density subset sum problems and has two major advantages over the method of Lagarias and Odlyzko: running time is an order of magnitude smaller and higher-density subset sum problems are solved.