Gennady Diubin, Alexander Korbut
On the average behaviour of greedy algorithms for the knapsack problem
Preprint series: Institut für Mathematik, Humboldt-Universität zu Berlin (ISSN 0863-0976)

MSC:

90C10 Integer programming

Abstract: 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 b of the constraint depends linearly on n, i.e., b = λ n. It is shown that if λ > 1/t - t/3 , then the primal and the dual greedy algorithms have an asymptotical tolerance t.
Keywords: Knapsack problem, greedy algorithm, average behaviour, asymptotic tolerance