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

Abstract

This paper is a partial generalization of the results of [3] for rather arbitrary distributions of coefficients. We state the main theorem concerning the average behaviour of greedy algorithms. The validity of this theorem is implied by the validity of the Conditions 1 and 2 from [3]. We give a detailed proof of Condition 1. The characterization of distributions for which Condition 2 holds will be the subject of a forthcoming paper.