The average behaviour of greedy algorithms for the knapsack problem: Computational experiments

Bernd Bank

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

MSC 2000

90C09 Boolean programming

90C27 Combinatorial optimization

Abstract
We describe primal and dual greedy algorithms for the one-dimensional knapsack problem with Boolean variables. A theorem concerning their average behaviour is formulated. It is supposed that all coefficients of the problem are independent random variables uniformly distributed on [0,1], and $b=\lambda n$. The theorem asserts that for $\lambda$ exceeding the "critical" value $1/2 - t/3$ both algorithms have asymptotical tolerance $t$. The main goal of the experiments was clarifying the behaviour of the algorithms for pre-critical value of $\lambda$. A brief characterization of a computer program implementing these methods together with preliminary results of the experiments is given. These results confirm the good behaviour of both methods and suggest some interesting theoretical problems.