An approximation algorithm for square packing.

DOI10.1016/J.ORL.2004.02.003MaRDI QIDQ703277zbMATH OpenOpenAlexFDO

Authors Rob van Stee

Publication date 11 January 2005

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.orl.2004.02.003

zbMATH Keywords

Approximation algorithmBin packingAbsolute worst-case ratioSquare packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Approximation algorithms (68W25) Discrete location and assignment (90B80)

Recommendations

• A Polynomial Time Approximation Scheme for the Square Packing Problem
• A 3-approximation algorithm for two-dimensional bin packing
• Absolute approximation ratios for packing rectangles into bins
• Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
• Algorithms for Packing Squares: A Probabilistic Analysis

Cites work

• scientific article; zbMATH DE number 3557207 (Why is no real title available?)
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Approximation schemes for multidimensional packing
• Bin packing can be solved within 1+epsilon in linear time
• New approximability and inapproximability results for 2-dimensional bin packing
• New bounds for multidimensional packing
• On Packing Two-Dimensional Bins
• On packing of squares and cubes
• Online algorithms. The state of the art

Cited in

(17)

• Algorithms for Packing Squares: A Probabilistic Analysis
• An algorithm for packing squares
• A linear approximation algorithm for bin packing with absolute approximation factor \(\frac {3}{2}\)
• Minimum tiling of a rectangle by squares
• Complexity and approximation of an area packing problem
• Packing squares with profits
• 2D knapsack: packing squares
• Improved approximation algorithms for rectangle tiling and packing.
• Dynamic multi-dimensional bin packing
• Two-dimensional packing with conflicts
• Absolute approximation ratios for packing rectangles into bins
• Approximation Algorithms for Maximizing the Number of Squares Packed into a Rectangle
• Packing Rectangles into 2OPT Bins Using Rotations
• Packing squares independently
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• 2D knapsack: packing squares
• Algorithm Theory - SWAT 2004

This page was built for publication: An approximation algorithm for square packing.

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