Approximation algorithm for the Subset-sum problem

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

Subset-sum problem
     Exponential-time exact algorithm
     Exact algorithm - dynamic programming
     Greedy algorithm
Diophantine linear equation

Literature

Cormen T. H., Leiserson Ch. E., Rivest R. L. Introduction to Algorithms

The MIT Press, Cambridge, 1990