On Packing Rectangles with Resource Augmentation: Maximizing the Profit

Authors

  • 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

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

Downloads

How to Cite

Fishkin, A. V., Gerber, O., Jansen, K., & Solis-Oba, R. (2008). 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

Issue

Vol. 3 No. 1 (2008)

Section

Articles

License

The copyright of the submitted article is hereby transferred to “Preeminent Academic Facets Inc. (the “publisher”) to the extent possible by the laws in the respective countries of the author(s). The author(s) retain all other rights including the following: 1. Any patents and trademark rights. 2. Right to post a pre-print version of the paper on the author’s personal website which is not used for commercial purposes. The author(s) warrant that the work is original, it has not been published elsewhere, it is not currently under consideration for publication in any form, and it does not infringe any copyright laws. The signing author or agent further warrants that all authors, if applicable, have been informed of the terms of this agreement and obtained the approval and authority to sign the agreement.