The average behaviour of greedy algorithms for the knapsack problem: General distributions

The paper is a generalization of [4], [5] for arbitrary distributions of coefficients. It is supposed that the coefficients of the objective function and the constraint of the knapsack problem are independent identically distributed random variables having a density with support [0, 1], and the right-hand side of the constraint is proportional to the number of variables, i. e. b=λn. We establish a bound on λ (in terms of the given density and a parameter t > 0) ensuring that both the primal and the dual greedy algorithms have an asymptotic tolerance t. Copyright Springer-Verlag Berlin Heidelberg 2003