2005-11-02Buch DOI: 10.18452/2579
The average behaviour of greedy algorithms for the knapsack problem: Computational experiments
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II, Institut für Mathematik
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.
Dateien zu dieser Publikation