SubsetSum Problem Polynomialtime approximation algorithm PROBLEM
In the subsetsum 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 Exponentialtime 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 (YZ)/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 Subsetsum problem (OGA)/O<=Epsilon, where O is the optimal solution value and GA the value returned of APPROX_SUBSET_SUM
COMPARISON
For N=100;T=25557 and the array A. created by statements:
I compared the algorithms for solution of the Subsetsum 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
CONNECTIONS
Subsetsum problem
Exponentialtime 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
