Packing Weighted Rectangles into a Square

Abstract We consider the problem of packing a set of weighted rectangles into a unit size square frame [0, 1] × [0, 1] so as to maximize the total weight of the packed rectangles. We present polynomial time approximation schemes (PTASs) that, for any ε >0, find (1 - ε )-approximate solutions for two special cases of the problem. In the first case we pack a set of squares whose weights are equal to their areas. In the second case we pack a set of weighted rectangles into an augmented square frame [0, 1 + 3 ε ] × [0, 1 + 3 ε ].

Authors

• Aleksei V. Fishkin
• Olga Gerber
• Klaus Jansen
• Roberto Solis-Oba

Keywords

No keywords are indexed for this paper.