Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/325712 
Year of Publication: 
2022
Citation: 
[Journal:] Operations Research Perspectives [ISSN:] 2214-7160 [Volume:] 9 [Article No.:] 100211 [Year:] 2022 [Pages:] 1-9
Publisher: 
Elsevier, Amsterdam
Abstract: 
In the perfect rectangle packing problem, a set of rectangular items have to be placed inside a rectangular container without overlap or empty space. In this paper, we generate a large number of random instances and decide them all with an exact solving algorithm. Both an instance's solution probability and its hardness measured in recursions or system time, seems to critically depend on tmax a parameter in the generation procedure that assigns the maximally choosable random side lengths of items in the instance. We numerically characterize the solvability across instance sizes, and derive a rule for generating (un)solvable problem instances of arbitrary size.
Subjects: 
Problem structuring
Perfect rectangle packing
Solvability
Phase transition
NP-complete
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.