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

DOI10.1007/S11432-012-4702-8MaRDI QIDQ362160zbMATH OpenOpenAlexFDO

Authors Wenqi Huang, Tao Ye, Duan-bing Chen

Publication date 20 August 2013

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

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

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)

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.

Recommendations

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

Cites work

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

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)