An Improved LowDensity Subset Sum AlgorithmMatthijs J. Coster, Brian A. LaMacchia, Andrew M. Odlyzko, and ClausPeter Schnorr
AbstractThe general subset sum problem is NPcomplete. 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 nonzero vectors in special lattices. The LagariasOdlyzko algorithm would solve almost all subset sum problems of density <0.6463... in polynomial time if it could invoke a polynomialtime algorithm for finding the shortest nonzero vector in a lattice. This note shows that a simple modification of that algorithm would solve almost all problems of density <0.9408... if it could find shortest nonzero vectors in lattices. This modification also yields dramatic improvements in practice when it is combined with known lattice basis reduction algorithms. Full Text

