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

A class of generalized greedy algorithms is proposed for the solution of the {0,1} multi-kanpsack 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. The authors 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.