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 L3-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 L3-algorithm usually finds a vector which is much shorter than what is guaranteed by Fact 3.100. Hence, the L3-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 L3-algorithm

INPUT: a set of positive integers {01,02,... , an} 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 у = (yn+1) in B, do the following:

4.1 If yn+i = 0 and yi e f} for all i = 1,2,... , n, then do the following: For г = 1,2,... , n, set у,- +

If aixi = s> then retnrn(a solution is (xi,X2,... , xn)).

For г = 1,2,... , n, set xti--y* +

If X^=i aixi = s> then return(a solution is (xi,X2,... , xn)).

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, X2,... , xn) is a solution to the subset sum problem, the vector у = ^Г=г x^i ~ b«+i is in L. Note that y, e {-|, |} for

i = 1,2,n and yn+i = 0. Since ||y|| = + y + • • • + y,21+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 L3-algorithm finding a basis which includes this vector.

Algorithm 3.105 is not guaranteed to succeed. Assuming that the L3-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.

< Prev   CONTENTS   Source   Next >