New approximability results for two-dimensional bin packing (Q261358): Difference between revisions
From MaRDI portal
Created a new Item |
Changed an Item |
||
Property / review text | |||
The paper studies two-dimensional bin packing problems with or without rotations, where a set of rectangles has to be packed into the minimum number of unit squares. The authors develop a polynomial 1.5-approximation algorithm that improves the former best asymptotic approximation ratio and reduces the gap between the known upper and lower bounds. A deep structural analysis of an arbitrary solution is given and it is shown how to round up the sizes of the rectangles to obtain a much more simple solution. The authors use the rounding technique similar to [\textit{C. Kenyon} and \textit{E. Rémila}, Math. Oper. Res. 25, No. 4, 645--656 (2000; Zbl 0977.90043)]. The developed algorithm packs rectangles with linear programs and with Next Fit Decreasing Height [\textit{E. G. Coffman jun.} et al., SIAM J. Comput. 9, 808--826 (1980; Zbl 0447.68079)]. | |||
Property / review text: The paper studies two-dimensional bin packing problems with or without rotations, where a set of rectangles has to be packed into the minimum number of unit squares. The authors develop a polynomial 1.5-approximation algorithm that improves the former best asymptotic approximation ratio and reduces the gap between the known upper and lower bounds. A deep structural analysis of an arbitrary solution is given and it is shown how to round up the sizes of the rectangles to obtain a much more simple solution. The authors use the rounding technique similar to [\textit{C. Kenyon} and \textit{E. Rémila}, Math. Oper. Res. 25, No. 4, 645--656 (2000; Zbl 0977.90043)]. The developed algorithm packs rectangles with linear programs and with Next Fit Decreasing Height [\textit{E. G. Coffman jun.} et al., SIAM J. Comput. 9, 808--826 (1980; Zbl 0447.68079)]. / rank | |||
Normal rank | |||
Property / reviewed by | |||
Property / reviewed by: Svetlana A. Kravchenko / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C27 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 68W25 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B10 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90B80 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C05 / rank | |||
Normal rank | |||
Property / Mathematics Subject Classification ID | |||
Property / Mathematics Subject Classification ID: 90C10 / rank | |||
Normal rank | |||
Property / zbMATH DE Number | |||
Property / zbMATH DE Number: 6559780 / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
bin packing | |||
Property / zbMATH Keywords: bin packing / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
rectangle packing | |||
Property / zbMATH Keywords: rectangle packing / rank | |||
Normal rank | |||
Property / zbMATH Keywords | |||
approximation algorithms | |||
Property / zbMATH Keywords: approximation algorithms / rank | |||
Normal rank |
Revision as of 14:29, 27 June 2023
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New approximability results for two-dimensional bin packing |
scientific article |
Statements
New approximability results for two-dimensional bin packing (English)
0 references
23 March 2016
0 references
The paper studies two-dimensional bin packing problems with or without rotations, where a set of rectangles has to be packed into the minimum number of unit squares. The authors develop a polynomial 1.5-approximation algorithm that improves the former best asymptotic approximation ratio and reduces the gap between the known upper and lower bounds. A deep structural analysis of an arbitrary solution is given and it is shown how to round up the sizes of the rectangles to obtain a much more simple solution. The authors use the rounding technique similar to [\textit{C. Kenyon} and \textit{E. Rémila}, Math. Oper. Res. 25, No. 4, 645--656 (2000; Zbl 0977.90043)]. The developed algorithm packs rectangles with linear programs and with Next Fit Decreasing Height [\textit{E. G. Coffman jun.} et al., SIAM J. Comput. 9, 808--826 (1980; Zbl 0447.68079)].
0 references
bin packing
0 references
rectangle packing
0 references
approximation algorithms
0 references