Band einer Schriftenreihe
Autor(en):
Gennady Diubin; Alexander Korbut Titel:
On the average behaviour of greedy algorithms for the knapsack problem Erscheinungsjahr:
1999 Erschienen in:
Preprints aus dem Institut für Mathematik 14	(Mathematik-Preprints)
Mathematik Schlagwörter (eng):
average behaviour, Knapsack problem, greedy algorithm, asymptotic tolerance 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/2 - t/3 , then the primal and the dual greedy algorithms have an asymptotical tolerance t. Gesamtzahl der Zugriffe seit Aug 2011: Startseite – 12 (0.31 pro Monat)
PDF – 391 (7.82 pro Monat)