id: 01264402
dt: a
an: 01264402
au: Diubin, Gennady; Korbut, Alexander
ti: On the average behaviour of primal and dual greedy algorithms for the
    knapsack problem.
so: Zimmermann, Uwe (ed.) et al., Operations research proceedings 1996.
    Selected papers of the symposium, SOR’96, Braunschweig, Germany,
    September 3-6, 1996. Berlin: Springer. 55-60 (1997).
py: 1997
pu: Berlin: Springer
la: EN
cc: 
ut: average behaviour; greedy algorithms; knapsack problem; Boolean variables;
    primal; dual
ci: 
li: 
ab: Summary: We consider primal (“best-in”) and dual (“worst-out”)
    greedy algorithms for the knapsack problem with Boolean variables. For
    the primal greedy algorithms, the worst-case behaviour is well-known,
    for the dual greedy algorithm it can be arbitrarily bad. We study the
    average performance of both algorithms. It is shown (on the basis of
    the central limit theorem) that in average the objective function value
    of the dual greedy algorithm differs insignificantly from the objective
    function value of the linear relaxation (and hence from the primal
    greedy and the optimal objective function values). This means that both
    the primal and the dual greedy algorithms are in a certain sense
    asymptotically optimal.
rv: