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

The paper is a generalization of earlier work on the knapsack problem 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-and 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.