# Solving subset sum problems of low density

The density of a knapsack set, as defined below, provides a measure of the size of the knapsack elements.

3.104 Definition Let 5 = {01,02,... , *a„* } be a knapsack set. The *density* of *S* is defined to be

Algorithm 3.105 reduces the subset sum problem to one of finding a particular short vector in a lattice. By Fact 3.100, the reduced basis produced by the L^{3}-algorithm includes a vector of length which is guaranteed to be within a factor of *2 ^{(n}~*

^{1 ,/<2}of the shortest nonzero vector of the lattice. In practice, however, the L

^{3}-algorithm usually finds a vector which is much shorter than what is guaranteed by Fact 3.100. Hence, the L

^{3}-algorithm can be expected to find the short vector which yields a solution to the subset sum problem, provided that this vector is shorter than most of the non-zero vectors in the lattice.

3.105 Algorithm Solving subset sum problems using L^{3}-algorithm

INPUT: a set of positive integers {01,02,... , *a _{n}}* and an integer

*s.*

OUTPUT: *Xi* e {0,1}, 1 < *i < n,* such that X^=i * ^{aiXi = s}>* provided such

*Xi*exist.

- 1. Let rn =
*^/n-* - 2. Form an (n +1 )-dimensional lattice
*L*with basis consisting of the rows of the matrix

- 3. Find a reduced basis
*В*of*L*(use Algorithm 3.101). - 4. For each vector
*у =*(y_{n}+1) in*B,*do the following:

4.1 If *y _{n+}i =* 0 and

*yi*e f} for all

*i*= 1,2,... , n, then do the following: For

*г =*1,2,... , n, set у,- +

If * ^{a}i^{x}i* =

*then retnrn(a solution is*

^{s}>*(xi,X*

*2*,... ,

*x*

_{n})).For *г =* 1,2,... , n, set *x _{t}i*--y* +

If X^=i * ^{a}i^{x}i* =

^{s}> then return(a solution is

*(xi,X*

*2*,... ,

*x*

_{n})).5. Retum(FAILURE). (Either no solution exists, or the algorithm has failed to find one.)

*Justification.* Let the rows of the matrix *A* be *b,* i>2,... , *b„+i,* and let *L* be the (n + 1)- dimensional lattice generated by these vectors. If (zi, *X**2*,... , *x _{n})* is a solution to the subset sum problem, the vector

*у =*^Г=г

*b«+i is in*

^{x}^i ~*L.*Note that

*y,*e {-|, |} for

*i* = 1,2*,n* and *y _{n+}i =* 0. Since ||y|| = +

*y*+ • • • + y,

^{2}1+1 the vector у is a

vector of shoif length in *L.* If the density of the knapsack set is small, i.e. the *a,* are large, then most vectors in *L* will have relatively large lengths, and hence у may be the unique shortest non-zero vector in *L.* If this is indeed the case, then there is good possibility of the L^{3}-algorithm finding a basis which includes this vector.

Algorithm 3.105 is not guaranteed to succeed. Assuming that the L^{3}-algorithm always produces a basis which includes the shortest non-zero lattice vector, Algorithm 3.105 succeeds with high probability if the density of the knapsack set is less than 0.9408.