Vol 3 No 1 (2008)
Articles

On Packing Rectangles with Resource Augmentation: Maximizing the Profit

Aleksei V. Fishkin
Max-Planck-Institut für Informatik, Stuhlsatzenhausweg 85, 66123 Saarbrücken, Germany.
Olga Gerber
University of Kiel, Olshausenstr. 40, 24118 Kiel, Germany.
Klaus Jansen
University of Kiel, Olshausenstr. 40, 24118 Kiel, Germany.
Roberto Solis-Oba
Department of Computer Science, The University of Western Ontario, London, Ontario, N6A 5B7, Canada.
Keywords
  • Rectangle packing,
  • approximation algorithms,
  • resource augmentation
How to Cite
Fishkin, A. V., Gerber, O., Jansen, K., & Solis-Oba, R. (1). On Packing Rectangles with Resource Augmentation: Maximizing the Profit. Algorithmic Operations Research, 3(1). Retrieved from https://journals.lib.unb.ca/index.php/AOR/article/view/5664

Abstract

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 ε.