×

Rectangle packing with additional restrictions. (English) Zbl 1227.68032

Summary: We formulate a generalization of the NP-complete rectangle packing problem by parameterizing it in terms of packing density, the ratio of rectangle areas, and the aspect ratio of individual rectangles. Then we show that almost all restrictions of this problem remain NP-complete and identify some cases where the answer to the decision problem can be found in constant time.

MSC:

68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Clautiaux, François; Carlier, Jacques; Moukrim, Aziz, A new exact method for the two-dimensional orthogonal packing problem, European Journal of Operational Research, 183, 3, 1196-1211 (2007) · Zbl 1135.90045
[2] Clautiaux, François; Jouglet, Antoine; Carlier, Jacques; Moukrim, Aziz, A new constraint programming approach for the orthogonal packing problem, Computers & Operations Research, 35, 3, 944-959 (2008), Part Special Issue: New Trends in Locational Analysis. · Zbl 1278.90147
[3] Demaine, Erik D.; Demaine, Martin L., Jigsaw puzzles, edge matching, and polyomino packing: connections and complexity, Graphs and Combinatorics, 23, 1, 195-208 (2007) · Zbl 1123.05027
[4] Dyckhoff, Harald, A typology of cutting and packing problems, European Journal Of Operational Research, 44, 2, 145-159 (1990) · Zbl 0684.90076
[5] Erdős, Paul, A theorem of Sylvester and Schur, Journal of the London Mathematical Society, s1-9, 4, 282-288 (1934) · Zbl 0010.10302
[6] Erdős, Paul; Szekeres, George, A combinatorial problem in geometry, Compositio Mathematica, 2, 463-470 (1935) · Zbl 0012.27010
[7] Sándor P. Fekete, Jörg Schepers, Jan van der Veen, An exact algorithm for higher-dimensional orthogonal packing. CoRR, abs/cs/0604045, 2006.; Sándor P. Fekete, Jörg Schepers, Jan van der Veen, An exact algorithm for higher-dimensional orthogonal packing. CoRR, abs/cs/0604045, 2006.
[8] Hougardy, Stefan, On packing squares into a rectangle, Computational Geometry, 44, 8, 456-463 (2011) · Zbl 1231.52011
[9] Joncour, Cédric; Pâcher, Arnaud; Valicov, Petru, Mpq-trees for orthogonal packing problem, Electronic Notes in Discrete Mathematics, 36, 423-429 (2010), ISCO 2010 — International Symposium on Combinatorial Optimization · Zbl 1237.90003
[10] Karp, Richard, Reducibility among combinatorial problems, (Miller, R.; Thatcher, J., Complexity of Computer Computations (1972), Plenum Press), 85-103 · Zbl 1187.90014
[11] Daniel J. Kleitman, Michael M. Krieger, An optimal bound for two dimensional bin packing, in: 16th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1975, 1975, pp. 163-168.; Daniel J. Kleitman, Michael M. Krieger, An optimal bound for two dimensional bin packing, in: 16th Annual IEEE Symposium on Foundations of Computer Science, FOCS 1975, 1975, pp. 163-168.
[12] Korf, Richard; Moffitt, Michael; Pollack, Martha, Optimal rectangle packing, Annals of Operations Research, 179, 261-295 (2010), 10.1007/s10479-008-0463-6 · Zbl 1201.90172
[13] Leung, Joseph Y.-T.; Tam, Tommy W.; Wong, C. S.; Young, Gilbert H.; Chin, Francis Y. L., Packing squares into a square, Journal of Parallel and Distributed Computing, 10, 3, 271-275 (1990)
[14] Keqin Li, Kam Hoi Cheng, Complexity of resource allocation and job scheduling problems in partitionable mesh connected systems, in: Proceedings of the First Annual IEEE Symposium of Parallel and Distributed Processing, 1989, pp. 358-365.; Keqin Li, Kam Hoi Cheng, Complexity of resource allocation and job scheduling problems in partitionable mesh connected systems, in: Proceedings of the First Annual IEEE Symposium of Parallel and Distributed Processing, 1989, pp. 358-365.
[15] Meir, Aram; Moser, Leo, On packing of squares and cubes, Journal of Combinatorial Theory, 5, 126-134 (1968) · Zbl 0165.25202
[16] Michael D. Moffitt, Martha E. Pollack, Optimal rectangle packing: a meta-CSP approach, in: Proceedings of the 16th International Conference on Automated Planning and Scheduling, ICAPS 2006, 2006, pp. 93-102.; Michael D. Moffitt, Martha E. Pollack, Optimal rectangle packing: a meta-CSP approach, in: Proceedings of the 16th International Conference on Automated Planning and Scheduling, ICAPS 2006, 2006, pp. 93-102.
[17] Moon, John W.; Moser, Leo, Some packing and covering theorems, Colloquium Mathematicum, 17, 103-110 (1967) · Zbl 0152.39502
[18] Novotný, Pavel, On packing of squares into a rectangle, Archivum Mathematicum, 32, 75-83 (1996) · Zbl 0905.52003
[19] Wäscher, Gerhard; Haußner, Heike; Schumann, Holger, An improved typology of cutting and packing problems, European Journal Of Operational Research, 183, 3, 1109-1130 (2007) · Zbl 1278.90347
[20] Jan Zernisch, A generalization of a theorem of Kleitman and Krieger. Technical Report 101018, Research Institute for Discrete Mathematics, University of Bonn, 2011.; Jan Zernisch, A generalization of a theorem of Kleitman and Krieger. Technical Report 101018, Research Institute for Discrete Mathematics, University of Bonn, 2011. · Zbl 1251.68291
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.