Subset-Sum Problem
Polynomial-time approximation algorithm

PROBLEM
In the subset-sum problem we wish to find a subset of A.1,...,A.N whose sum is as large as possible but not larger than T (capacity of the knapsack).

ALGORITHM
This algorithms is evolved from Exponential-time exact algorithm. We use a trimming parametr Delta such that 0<Delta<1. To "trim" a list L. by Delta means to remove as many elements from L. as possible, in such a way that for every element Y that was removed from L. there is an element Z<=Y in L. such that (Y-Z)/Y<=Delta. The element Z is representing Y in the new list. Cormen, Leiserson and Rivest credit O. H. Ibarra and Ch. E. Kim with inventing the APPROX_SUBSET_SUM function.

IMPLEMENTATION
Unit: internal function
 
Global variables: array A.1,...,A.N of integers, array A. is not changed
 
Parameters: a positive integer N, a positive integer T, a real Epsilon (0<Epsilon<1)
 
Returns: good approximation of largest sum of subset <=T, for any instance of the Subset-sum problem (O-GA)/O<=Epsilon, where O is the optimal solution value and GA the value returned of APPROX_SUBSET_SUM
 

APPROX_SUBSET_SUM: procedure expose A.
parse arg N, T, Epsilon
L.1 = 0; P = 1; Sentinel = 1E+100
do I = 1 to N while A.I <= T
  do J = 1 to P
    LP.J = L.J + A.I
    if LP.J > T then leave J
  end
  R = J - 1; K = 1; L = 1
  Pp1 = P + 1
  L.Pp1 = Sentinel
  LP.J = Sentinel
  do M = 1 to P + R
    if L.K < LP.L
      then do; M.M = L.K; K = K + 1; end
      else do; M.M = LP.L; L = L + 1; end
  end
  do J = 1 to P + R; L.J = M.J; end
  P = TRIM(P + R, Epsilon / N)
end
return L.P
 
TRIM: procedure expose M. L.
parse arg M, Delta
L.1 = M.1; Last = M.1; P = 1
do I = 2 to M
  if Last < (1 - Delta) * M.I
    then do
      P = P + 1; L.P = M.I; Last = M.I
    end
  end
return P

 

COMPARISON
For N=100;T=25557 and the array A. created by statements:

Seed = RANDOM(1, 1, 481989)
do J = 1 to N
  A.J = RANDOM(1, 1000)
end

I compared the algorithms for solution of the Subset-sum problem and my algorithm DIOPHANT for solution of the diophantine equations.

Notes:
I halted the EXACT_SUBSET_SUM after 30 minutes of computations. For APPROX_SUBSET_SUM I used the value Epsilon=0.5

 

Subset-sum problem - Comparison of Algorithms
Algorithm Subset sum Seconds
GS 25554      0.05 
DPS 25557   240.24 
APPROX_SUBSET_SUM 25436    12.31 
DIOPHANT 25557      0.82 

 

CONNECTIONS

Literature
Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms
The MIT Press, Cambridge, 1990


Cover Contents Index Main page

last modified 8th August 2001
Copyright 2000-2001 Vladimir Zabrodsky
Czech Republic