On Packing Squares with Resource Augmentation: Maximizing the Profit

Fishkin, A.V., Gerber, O., Jansen, K. and Solis-Oba, R.

We consider the problem of packing squares with profits into a bounded square region so as to maximize their total profit. More specifically, given a set L of n squares with positive profits, it is required to pack a subset of them into a unit size square region [0,1] X [0,1] so that the total profit of the squares packed is maximized. For any given positive accuracy e >0, we present an algorithm that outputs a packing of a subset of L in the augemented square region [1 + e] X [1 + e] with profit value at least (1 - e)OPT(L), where OPT(L) is the maximum profit that can be achieved by packing a subset of L in the unit square. The running time of the algorithm is polynomial in n for fixed e.

Cite as: Fishkin, A.V., Gerber, O., Jansen, K. and Solis-Oba, R. (2005). On Packing Squares with Resource Augmentation: Maximizing the Profit. In Proc. Eleventh Computing: The Australasian Theory Symposium (CATS2005), Newcastle, Australia. CRPIT, 41. Atkinson, M. and Dehne, F., Eds. ACS. 61-67.

(from crpit.com) (local if available)