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

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.