Two for One: Tight Approximation of 2D Bin Packing

DOI10.1007/978-3-642-03367-4_35zbMath1253.68361OpenAlexW136402461MaRDI QIDQ3183471

Ulrich M. Schwarz, Lars Prädel, Klaus Jansen

Publication date: 20 October 2009

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-03367-4_35

zbMATH Keywords

approximationbin packingrectangle packing

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Approximation algorithms (68W25)

Related Items (5)

Packing anchored rectangles ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A \((5/3+\varepsilon)\)-approximation for strip packing ⋮ Number of bins and maximum lateness minimization in two-dimensional bin packing ⋮ New approximability results for two-dimensional bin packing

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Maximizing the total profit of rectangles packed into a rectangle
• Approximating the advertisement placement problem
• A 3-approximation algorithm for two-dimensional bin packing
• A Near-Optimal Solution to a Two-Dimensional Cutting Stock Problem
• A Polynomial Time Approximation Scheme for the Square Packing Problem
• Packing Rectangles into 2OPT Bins Using Rotations
• New Approximability Results for 2-Dimensional Packing Problems
• A Structural Lemma in 2-Dimensional Packing, and Its Implications on Approximability
• Orthogonal Packings in Two Dimensions
• A algorithm for two-dimensional packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Bounds on Multiprocessing Timing Anomalies

This page was built for publication: Two for One: Tight Approximation of 2D Bin Packing