TY - JOUR
AU - Fishkin, Aleksei V.
AU - Gerber, Olga
AU - Jansen, Klaus
AU - Solis-Oba, Roberto
PY - 2008/03/27
Y2 - 2023/11/30
TI - On Packing Rectangles with Resource Augmentation: Maximizing the Profit
JF - Algorithmic Operations Research
JA - AOR
VL - 3
IS - 1
SE - Articles
DO -
UR - https://journals.lib.unb.ca/index.php/AOR/article/view/5664
SP -
AB - We consider the problem of packing rectangles with profits into a bounded square region so as to maximize their total profit. More specifically, given a set R of n rectangles with positive profits, it is required to pack a subset of them into a unit size square frame [0,1] x [0,1] so that the total profit of the rectangles packed is maximized. For any given positive accuracy ε > 0, we present an algorithm that outputs a packing of a subset of R in the augmented square region [1 + ε] x [1 + ε] with profit value at least (1 - ε)OPT, where OPT is the maximum profit that can be achieved by packing a subset of R in a unit square frame. The running time of the algorithm is polynomial in n for fixed ε.
ER -