期刊
OPERATIONS RESEARCH LETTERS
卷 32, 期 1, 页码 5-14出版社
ELSEVIER SCIENCE BV
DOI: 10.1016/S0167-6377(03)00057-9
关键词
two-dimensional knapsack; upper bound; approximation algorithm; worst-case performance; exact algorithm
We address the two-dimensional Knapsack Problem (2YP), 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. (C) 2003 Elsevier B.V. All rights reserved.
作者
我是这篇论文的作者
点击您的名字以认领此论文并将其添加到您的个人资料中。
推荐
暂无数据