Approximation schemes for the subset-sum problem: Survey and experimental analysis (Q1069445)

Given n positive integers \(w_ 1,\ldots,w_ n\) and a positive integer W the subset-sum problem (SSP) is to find a subset of \(N=\{1,\ldots,n\}\) so as to max\(\sum_{i\in S}w_ i\) s.t. \(\sum_{i\in S}w_ i\leq W\). The best-known heuristics for this problem are approximation schemes based on worst-case analysis (WCA) which establishes the maximum relative error the algorithm can produce. WCA is based on the following definition of worst-case performance ratio r(H): it is the largest number smaller or equal to H(I)/Z(I) for all possible instances I of SSP, Z(I) is the value of optimal solution of problem I, H(I) is the value of the solution found by a heuristic algorithm H when applied to problem I. The polynomial approximation schemes of Johnson, Martello and Toth, fully polynomial approximation schemes of Lawler and Gens and Levner are experimentally examined. The results of computational experiments (the code was written in FORTRAN IV and was run on a CDC Cyber 730) have shown that all the approximate algorithms for SSP have an average performance much better than their worst-case performance. Although polynomial approximation schemes have a worse bound on computing time, their average performance appears superior to that of the fully polynomial approximation schemes. The most effective scheme is that proposed by the authors.