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

Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976),

MSC 2000

90C09 Boolean programming

90C27 Combinatorial optimization

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.

Keywords: knapsack problems, greedy algorithms, average behaviour

Notes
[3] Diubin, G.N., A.A. Korbut; On the average behaviour of greedy algorithms for the knapsack problem. Preprint 99-14, Humboldt-Universitaet zu Berlin, Mathematisch-Naturwissenschaftliche Fakultaet II, Institut fuer Mathematik, 1999