Name
Abstract | ||
|---|---|---|
We address the two-dimensional Knapsack Problem (2KP), aimed at packing a maximum-profit subset of rectangles selected from a given set into another rectangle. We consider the natural relaxation of 2KP given by the one-dimensional KP with item weights equal to the rectangle areas, proving the worst-case performance of the associated upper bound, and present and compare computationally four exact algorithms based on the above relaxation, showing their effectiveness. |
Year | DOI | Venue |
|---|---|---|
2004 | 10.1016/S0167-6377(03)00057-9 | Oper. Res. Lett. |
Keywords | Field | DocType |
worst-case performance,two-dimensional knapsack,natural relaxation,upper bound,approximation algorithm,one-dimensional kp,maximum-profit subset,exact algorithm,two-dimensional knapsack problem,rectangle area,item weight,knapsack problem,profitability | Discrete mathematics,Approximation algorithm,Combinatorics,Mathematical optimization,Exact algorithm,Upper and lower bounds,Change-making problem,Continuous knapsack problem,Cutting stock problem,Knapsack problem,Polynomial-time approximation scheme,Mathematics | Journal |
Volume | Issue | ISSN |
32 | 1 | Operations Research Letters |
Citations | PageRank | References |
57 | 2.78 | 9 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alberto Caprara | 1 | 98 | 5.23 |
| Michele Monaci | 2 | 1049 | 60.78 |