On Packing Rectangles with Resource Augmentation:: Maximizing the Profit - Fishkin, Aleksei; Gerber, Olga; Jansen, Klaus; Solis-Oba, Roberto (Algorithmic Operations Research)

(untitled) (Preeminent Academic Facets Inc., 2008)
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] × [0,1] so that the total profit of the rectangles packed is maximized. For any given positive accuracy [.epsilon] > 0, we present an algorithm that outputs a packing of a subset of R in the augmented square region [1 + [.epsilon]] × [1 + [.epsilon]] with profit value at least (1 − [.epsilon])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 [.epsilon].