Absolute approximation ratios for packing rectangles into bins

DOI10.1007/S10951-009-0110-3zbMath1280.68295OpenAlexW1996647916MaRDI QIDQ2434269

Rob van Stee, Rolf Harren

Publication date: 5 February 2014

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10951-009-0110-3

zbMATH Keywords

approximation algorithmbin packingrectangle packingabsolute worst-case ratio

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items (4)

Polynomial-time approximation schemes for circle and other packing problems ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ Two-dimensional online bin packing with rotation ⋮ New approximability results for two-dimensional bin packing

Cites Work

• An approximation algorithm for square packing.
• Maximizing the total profit of rectangles packed into a rectangle
• A 3-approximation algorithm for two-dimensional bin packing
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• Inapproximability Results for Orthogonal Rectangle Packing Problems with Rotations
• New Approximability Results for 2-Dimensional Packing Problems
• On strip packing With rotations
• Performance Bounds for Level-Oriented Two-Dimensional Packing Algorithms
• On Packing Two-Dimensional Bins
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes
• On packing of squares and cubes
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing

This page was built for publication: Absolute approximation ratios for packing rectangles into bins