An approximation scheme for the two-stage, two-dimensional knapsack problem

被引：3

作者：

Caprara, Alberto ^{[1
]}

Lodi, Andrea ^{[1
]}

Monaci, Michele ^{[2
]}

机构：

[1] Univ Bologna, DEIS, I-40136 Bologna, Italy

[2] Univ Padua, DEIS, I-35131 Padua, Italy

来源：

DISCRETE OPTIMIZATION | 2010年 / 7卷 / 03期

关键词：

Knapsack problem; Shelf packing; Polynomial time approximation schemes; BIN PACKING; SUM;

D O I：

10.1016/j.disopt.2010.03.003

中图分类号：

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

学科分类号：

070105 ; 12 ; 1201 ; 1202 ; 120202 ;

摘要：

We present an approximation scheme for the two-dimensional version of the knapsack problem which requires packing a maximum-area set of rectangles in a unit square bin, with the further restrictions that packing must be orthogonal without rotations and done in two stages. Achieving a solution which is close to the optimum modulo a small additive constant can be done by taking wide inspiration from an existing asymptotic approximation scheme for two-stage two-dimensional bin packing. On the other hand, getting rid of the additive constant to achieve a canonical approximation scheme appears to be widely nontrivial. (C) 2010 Elsevier B.V. All rights reserved.

引用

页码：114 / 124

页数：11

共 12 条

[1]

[Anonymous], 1999, COMPLEXITY APPROXIMA, DOI DOI 10.1007/978-3-642-58412-1

[2]

BANSAL N, 2009, SPRINGER LECT NOTES, V5878

[3] The multiple subset sum problem [J].