Solving subset sum problems with the L^3 algorithm

Show full item record

Redirect: RIT Scholars content from RIT Digital Media Library has moved from to RIT Scholar Works, please update your feeds & links!
Title: Solving subset sum problems with the L^3 algorithm
Author: Radziszowski, Stanislaw; Kreher, Donald
Abstract: Ideas are described that speed up the lattice basis reduction algorithm of Lenstra, Lenstra and Lovasz [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 Lararias and Odlyzko: running time is an order of magnitude smaller and higher density subset sum problems are solved.
Record URI:
Date: 1988

Files in this item

Files Size Format View
SRadziszowskiArticle04-1988.pdf 1.414Mb PDF View/Open

The following license files are associated with this item:

This item appears in the following Collection(s)

Show full item record

Search RIT DML

Advanced Search