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

Given a set of n positive integers w₁,…,w_n and a positive integer W, the Subset-Sum Problem is to find that subset whose sum is closest to, without exceeding, W. The most important heuristics for this problem are approximation schemes based on a worst-case analysis. We survey them and experimentally analyze their statistical behaviour on a large number of test problems.