An Improved Low-Density Subset Sum Algorithm

M. J. Coster  ¹
B. A. LaMacchia  ²
A. M. Odlyzko

AT&T Bell Laboratories
Murray Hill, New Jersey 07974

C. P. Schnorr

Universität Frankfurt
Fachbereich Mathematik/Informatik
Postfach 11 19 32
6000 Frankfurt am Main
Germany

ABSTRACT

The general subset sum problem is NP-complete. However, there are two algorithms, one due to Brickell and the other to Lagarias and Odlyzko, which in polynomial time solve almost all subset sum problems of sufficiently low density. Both methods rely on basis reduction algorithms to find short non-zero vectors in special lattices. The Lagarias-Odlyzko algorithm would solve almost all subset sum problems of density $< 0.6463\ldots{}$ in polynomial time if it could invoke a polynomial-time algorithm for finding the shortest non-zero vector in a lattice. This note shows that a simple modification of that algorithm would solve almost all problems of density $< 0.9408\ldots{}$ if it could find shortest non-zero vectors in lattices. This modification also yields dramatic improvements in practice when it is combined with known lattice basis reduction algorithms.