A class of generalized greedy algorithms for the multi-knapsack problem

A.H.G. Rinnooy Kan, L. Stougie, C. Vercellis

    Onderzoeksoutput: Bijdrage aan tijdschriftTijdschriftartikelAcademicpeer review

    35 Citaten (Scopus)

    Samenvatting

    A class of generalized greedy algorithms is proposed for the solution of the [lcub]0,1[rcub] multi-knapsack problem. Items are selected according to decreasing ratios of their profit and a weighted sum of their requirement coefficients. The solution obtained depends on the choice of the weights. A geometrical representation of the method is given and the relation to the dual of the linear programming relaxation of multi-knapsack is exploited. We investigate the complexity of computing a set of weights that gives the maximum greedy solution value. Finally, the heuristics are subjected to both a worst-case and a probabilistic performance analysis.
    Originele taal-2Engels
    Pagina's (van-tot)279-290
    TijdschriftDiscrete Applied Mathematics
    Volume42
    Nummer van het tijdschrift2-3
    DOI's
    StatusGepubliceerd - 1993

    Vingerafdruk Duik in de onderzoeksthema's van 'A class of generalized greedy algorithms for the multi-knapsack problem'. Samen vormen ze een unieke vingerafdruk.

    Citeer dit