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.
An Approximation Scheme for Two-Stage, Two- Dimensional Knapsack / A. Caprara; A. Lodi; M. Monaci. - In: DISCRETE OPTIMIZATION. - ISSN 1572-5286. - STAMPA. - 7:(2010), pp. 114-124. [10.1016/j.disopt.2010.03.003]
An Approximation Scheme for Two-Stage, Two- Dimensional Knapsack
CAPRARA, ALBERTO;LODI, ANDREA;MONACI, MICHELE
2010
Abstract
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.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
