Stochastic analysis of greedy algorithms for the subset sum problem

The subset sum problem is the selection of a subset of items from a given ground set summing up as close as possible to a given capacity value. In this paper we deal with the probabilistic analysis of greedy algorithms for a subset sum problem where the items are drawn from a discrete uniform distribution. Starting from results by d'Atri and Puech we derive expected values for several crucial output parameters of these algorithms, in particular for the final gap between the heuristic solution value and the subset capacity. These expectations are given as explicit functions in the input size and a distribution parameter. This gives a more precise picture of the quality of a solution than an asymptotic statement.