Article ID: | iaor19981714 |
Country: | Netherlands |
Volume: | 84 |
Issue: | 3 |
Start Page Number: | 618 |
End Page Number: | 632 |
Publication Date: | Aug 1995 |
Journal: | European Journal of Operational Research |
Authors: | Zissimopoulos Vassilis, Fayard Didier |
Keywords: | knapsack problem |
An efficient heuristic for solving two-dimensional knapsack problems is proposed. The algorithm selects an optimal subset of optimal generated strips by solving a sequence of one-dimensional knapsack problems. We show that the number of these knapsacks can be reduced to only four knapsacks. The algorithm gives an excellent worst-case experimental approximation ratio (0.98), and a high percentage of optimal solutions (91%). From this heuristic, we derive an approximation algorithm for which we prove some refined bounds and we show that its approximation ratio is