Improved low-density subset sum algorithms (Q1207335)

The authors improve an algorithm of \textit{J. C. Lagarias} and \textit{A. M. Odlyzko} [J. Assoc. Comput. Mach. 32, 229-246 (1985)] which reduces the solution of a subset sum problem to the calculation of a shortest vector in a suitable lattice. The authors introduce two new lattices the use of which yields solutions for all subset sum problems of density \(< 0.9408\) (thus improving the old bound 0.6463 of Lagarias and Odlyzko).