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

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

doi:10.1016/0166-218X(93)90051-O

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

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

Onderzoeksoutput: Bijdrage aan tijdschrift › Tijdschriftartikel › Academic › peer 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-2	Engels
Pagina's (van-tot)	279-290
Tijdschrift	Discrete Applied Mathematics
Volume	42
Nummer van het tijdschrift	2-3
DOI's	https://doi.org/10.1016/0166-218X(93)90051-O
Status	Gepubliceerd - 1993

Toegang tot document

10.1016/0166-218X(93)90051-O

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

@article{a8e927e8d94b4850a6827a75e14c76eb,

title = "A class of generalized greedy algorithms for the multi-knapsack problem",

abstract = "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.",

author = "{Rinnooy Kan}, A.H.G. and L. Stougie and C. Vercellis",

year = "1993",

doi = "10.1016/0166-218X(93)90051-O",

language = "English",

volume = "42",

pages = "279--290",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier",

number = "2-3",

}

TY - JOUR

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

AU - Rinnooy Kan, A.H.G.

AU - Stougie, L.

AU - Vercellis, C.

PY - 1993

Y1 - 1993

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

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

U2 - 10.1016/0166-218X(93)90051-O

DO - 10.1016/0166-218X(93)90051-O

M3 - Article

VL - 42

SP - 279

EP - 290

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - 2-3

ER -