2005-11-07Buch DOI: 10.18452/2658
The average behaviour of greedy algorithms for the knapsack problem: General distributions
This paper is a partial generalization of the results of  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 . 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.
Files in this item