Corner occupying theorem for the two-dimensional integral rectangle packing problem

DOI10.1007/S11432-012-4702-8zbMATH Open1270.90056arXiv1111.3715OpenAlexW2963740413MaRDI QIDQ362160FDOQ362160

Authors: Wenqi Huang, Tao Ye, Duan-bing Chen 

Publication date: 20 August 2013

Published in: Science China Information Sciences (Search for Journal in Brave)

Abstract: This paper proves a corner occupying theorem for the two-dimensional integral rectangle packing problem, stating that if it is possible to orthogonally place n arbitrarily given integral rectangles into an integral rectangular container without overlapping, then we can achieve a feasible packing by successively placing an integral rectangle onto a bottom-left corner in the container. Based on this theorem, we might develop efficient heuristic algorithms for solving the integral rectangle packing problem. In fact, as a vague conjecture, this theorem has been implicitly mentioned with different appearances by many people for a long time.

Full work available at URL: https://arxiv.org/abs/1111.3715

Recommendations

• Optimal rectangle packing: an absolute placement approach
• Packing anchored rectangles
• On Two Dimensional Packing
• A new nonlinear model for the two-dimensional rectangle packing problem
• scientific article; zbMATH DE number 19811

zbMATH Keywords

rectangle packingbottom-leftcorner occupying theoremNP hard

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Exact algorithms for the two-dimensional strip packing problem with and without rotations
• Two-dimensional packing problems: a survey
• Orthogonal Packings in Two Dimensions
• An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
• Two-Dimensional Finite Bin-Packing Algorithms
• An Algorithm for Two-Dimensional Cutting Problems
• The Three-Dimensional Bin Packing Problem
• A New Placement Heuristic for the Orthogonal Stock-Cutting Problem
• An exact algorithm for general, orthogonal, two-dimensional knapsack problems
• A caving degree approach for the single container loading problem
• The Bottomn-Left Bin-Packing Heuristic: An Efficient Implementation
• A new heuristic algorithm for rectangle packing
• Exhaustive approaches to 2D rectangular perfect packings
• Erratum to “The Three-Dimensional Bin Packing Problem”: Robot-Packable and Orthogonal Variants of Packing Problems

This page was built for publication: Corner occupying theorem for the two-dimensional integral rectangle packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q362160)