On the two-dimensional knapsack problem

被引：82

作者：

Caprara, A ^{[1
]}

Monaci, M ^{[1
]}

机构：

[1] Univ Bologna, Dipartimento Elettr Informat & Sistemist, I-40136 Bologna, Italy

来源：

OPERATIONS RESEARCH LETTERS | 2004年 / 32卷 / 01期

关键词：

two-dimensional knapsack; upper bound; approximation algorithm; worst-case performance; exact algorithm;

D O I：

10.1016/S0167-6377(03)00057-9

中图分类号：

C93 [管理学]; O22 [运筹学];

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

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.

引用

页码：5 / 14

页数：10

共 22 条

[1]

BEASLEY JE, 1985, J OPER RES SOC, V36, P297

[2] AN EXACT TWO-DIMENSIONAL NON-GUILLOTINE CUTTING TREE-SEARCH PROCEDURE [J].