Packing into the smallest square: worst-case analysis of lower bounds

DOI10.1016/J.DISOPT.2006.06.001zbMATH Open1112.90066OpenAlexW1980099076MaRDI QIDQ865748FDOQ865748

Authors Alberto Caprara, Andrea Lodi, Silvano Martello, Michele Monaci 

Publication date 20 February 2007

Published in Discrete Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.disopt.2006.06.001

zbMATH Keywords

lower boundpackingexperimentsworst-case

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Recommendations

• Models and algorithms for packing rectangles into the smallest square
• Worst-case analysis of fast heuristics for packing squares into a square
• Optimal rectangle packing
• scientific article; zbMATH DE number 4198016
• Algorithm Theory - SWAT 2004

Cites Work

• scientific article; zbMATH DE number 3684430 (Why is no real title available?)
• scientific article; zbMATH DE number 1226257 (Why is no real title available?)
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A lower bound for the non-oriented two-dimensional bin packing problem
• Algorithms for Unconstrained Two-Dimensional Guillotine Cutting
• An Exact Two-Dimensional Non-Guillotine Cutting Tree Search Procedure
• An empirical investigation of meta-heuristic and heuristic algorithms for a 2D packing problem
• An exact algorithm for orthogonal 2-D cutting problems using guillotine cuts
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• Exact solution of the two-dimensional finite bin packing problem
• Resource augmentation in two-dimensional packing with orthogonal rotations
• Some packing and covering theorems
• Worst-case analysis of fast heuristics for packing squares into a square

Cited In (7)

• Minimum tiling of a rectangle by squares
• Logic based Benders' decomposition for orthogonal stock cutting problems
• Packing unequal rectangles and squares in a fixed size circular container using formulation space search
• Almost square packing
• Models and algorithms for packing rectangles into the smallest square
• Knapsack problems -- an overview of recent advances. II: Multiple, multidimensional, and quadratic knapsack problems
• Bounds on soft rectangle packing ratios

This page was built for publication: Packing into the smallest square: worst-case analysis of lower bounds

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