An approximation algorithm for solving unconstrained two-dimensional knapsack problems

An approximation algorithm for solving unconstrained two-dimensional knapsack problems

0.00 Avg rating0 Votes
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: ,
Keywords: knapsack problem
Abstract:

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 4/9. Our numerical study on large size instances shows the efficiency of these algorithms for solving real-world problems that are hardly handled by other known methods, which are often limited by computer storage facilities.

Reviews

Required fields are marked *. Your email address will not be published.