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

Gennady Diubin & Alexander Korbut
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.
This data repository is not currently reporting usage information. For information on how your repository can submit usage information, please see our documentation.