MFCS Conference 2005 Conference Paper
Packing Weighted Rectangles into a Square
- Aleksei V. Fishkin
- Olga Gerber
- Klaus Jansen
- Roberto Solis-Oba
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 ε ].