New approximability results for two-dimensional bin packing (Q261358): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(4 intermediate revisions by 4 users not shown) | |||
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 | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W2003941356 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved Approximation Algorithm for Two-Dimensional Bin Packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: APPROXIMATION ALGORITHMS FOR MULTIPLE STRIP PACKING AND SCHEDULING PARALLEL JOBS IN PLATFORMS / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Packing <i>d</i>-Dimensional Bins in <i>d</i> Stages / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Hardness of approximation for orthogonal rectangle packing and covering problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On Packing Two-Dimensional Bins / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5624995 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Carathéodory bounds for integer cones / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Bin packing can be solved within 1+epsilon in linear time / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximate Max-Min Resource Sharing for Structured Concave Optimization / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Absolute approximation ratios for packing rectangles into bins / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Improved Absolute Approximation Ratios for Two-Dimensional Packing Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Approximation Algorithms for Min-Max and Max-Min Resource Sharing Problems, and Applications / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A New Asymptotic Approximation Algorithm for 3-Dimensional Strip Packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Two for One: Tight Approximation of 2D Bin Packing / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Rectangle packing with one-dimensional resource augmentation / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On strip packing With rotations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Minkowski's Convex Body Theorem and Integer Programming / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Fast Approximation Algorithms for Knapsack Problems / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A Strip-Packing Algorithm with Absolute Performance Bound 2 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: An algorithm for linear programming which requires \(O(((m+n)n^ 2+(m+n)^{1.5}n)L)\) arithmetic operations / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: A 3-approximation algorithm for two-dimensional bin packing / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 16:44, 11 July 2024
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
0 references
0 references
0 references
0 references
0 references