Browsing Preprints aus dem Institut für Mathematik by Author "Diubin, Gennady"

Now showing items 1-3 of 3

2005-11-16Buch

On the average behaviour of greedy algorithms for the knapsack problem

Diubin, Gennady; Korbut, Alexander

We study the average behaviour of the well-known greedy algorithms for the one-dimensional knapsack problem with Boolean variables when the number of variables n tends to infinity. It is supposed that the right-hand side ...
2005-11-02Buch

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

Bank, Bernd; Diubin, Gennady; Korbut, Alexander; Sigal, I.

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 ...
2005-11-07Buch

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

Diubin, Gennady; Korbut, Alexander

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 ...