On the average behaviour of greedy algorithms for the knapsack problem

Abstract

We study the average behaviour of the well-known greedy algorithms for the one-dimensional knapsack problem with Boolean variables when the number of variables n tends to infinity. It is supposed that the right-hand side b of the constraint depends linearly on n, i.e., b = λ n. It is shown that if λ > 1/2 - t/3 , then the primal and the dual greedy algorithms have an asymptotical tolerance t.