On rectangle packing: maximizing benefits

ABSTRACT

We consider the following rectangle packing problem: Given a set of rectangles, each of which is associated with a profit, we are requested to pack a subset of the rectangles into a bigger rectangle to maximize the total profit of rectangles packed. The rectangles may not overlap and may or may not be rotated. This problem is strongly NP-hard even for packing squares with identical profits. A simple (3 + ε)-approximation algorithm is presented. We further improve the algorithm by showing a worst-case ratio of at most 5/2 + ε. Finally we devise a (2 + ε)-approximation algorithm. A number of restricted cases are also considered.

REFERENCES

• 1: B. S. Baker, A. R. Calderbank, E. G. Coffman, and J. C. Lagarias, Approximation algorithms for maximizing the number of squares packed into a rectangle, SIAM J. on Algebraic and Discrete Methods4 (1983), 383--397.
• 2: Gruia Calinescu , Amit Chakrabarti , Howard J. Karloff , Yuval Rabani, Improved Approximation Algorithms for Resource Allocation, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.401-414, May 27-29, 2002
• 3: W. Fernandez de la Vega and G. S. Luecker, Bin packing can be solved within 1 + ε in linear time, Combinatorica1 (1981), 349--355.
• 4: Ari Freund , Joseph Naor, Approximating the Advertisement Placement Problem, Proceedings of the 9th International IPCO Conference on Integer Programming and Combinatorial Optimization, p.415-424, May 27-29, 2002
• 5: A. M. Frieze and M. R. B. Clarke, Approximation algorithms for the m-dimensional 0-1 knapsack problem: worst-case and probabilistic analyses, European Journal of Operational Research15 (1984), 100--109.
• 6: Dorit S. Hochbaum , Wolfgang Maass, Approximation schemes for covering and packing problems in image processing and VLSI, Journal of the ACM (JACM), v.32 n.1, p.130-136, Jan. 1985 [doi>10.1145/2455.214106]
• 7: Oscar H. Ibarra , Chul E. Kim, Fast Approximation Algorithms for the Knapsack and Sum of Subset Problems, Journal of the ACM (JACM), v.22 n.4, p.463-468, Oct. 1975 [doi>10.1145/321906.321909]
• 8: Klaus Jansen , Lorant Porkolab, Improved Approximation Schemes for Scheduling Unrelated Parallel Machines, Mathematics of Operations Research, v.26 n.2, p.324-338, May 2001 [doi>10.1287/moor.26.2.324.10559]
• 9: K. Jansen and G. Zhang, Packing maximum number of rectangles into a rectangle, manuscript, 2003.
• 10: N. Karmarker and R. M. Karp, An efficient approximation scheme for the one-dimensional bin-packing problem, In Proc. 23rd Annual IEEE Symp. Found. Comput. Sci., pp 312--320, 1982.
• 11: Hans Kellerer , Ulrich Pferchy, A New Fully Polynomial Approximation Scheme for the Knapsack Problem, Proceedings of the International Workshop on Approximation Algorithms for Combinatorial Optimization, p.123-134, July 18-19, 1998
• 12: Joseph Y.-T. Leung , Tommy W. Tam , C. S. Wong , Gilbert H. Young , Francis Y.L. Chin, Packing squares into a square, Journal of Parallel and Distributed Computing, v.10 n.3, p.271-275, Nov. 1990 [doi>10.1016/0743-7315(90)90019-L]
• 13: Ingo Schiermeyer, Reverse-Fit: A 2-Optimal Algorithm for Packing Rectangles, Proceedings of the Second Annual European Symposium on Algorithms, p.290-299, September 26-28, 1994
• 14: David B. Shmoys , Éva Tardos, An approximation algorithm for the generalized assignment problem, Mathematical Programming: Series A and B, v.62 n.3, p.461-474, Dec. 8, 1993 [doi>10.1007/BF01585178]
• 15: D. Simchi-Levi, New worst-case results for the bin packing problem, Naval Research Logistics41 (1994), 579--585.
• 16: A. Steinberg, A Strip-Packing Algorithm with Absolute Performance Bound 2, SIAM Journal on Computing, v.26 n.2, p.401-409, April 1997 [doi>10.1137/S0097539793255801]