Two for one: tight approximation of 2D bin packing

DOI10.1142/S0129054113500354MaRDI QIDQ5168419zbMATH OpenOpenAlexFDO

Authors Rolf Harren, Lars Prädel, Ulrich M. Schwarz, Rob van Stee, Klaus Jansen

Publication date 4 July 2014

Published in International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1142/s0129054113500354

zbMATH Keywords

approximationbin packingrectangle packing

Mathematics Subject Classification ID

Approximation algorithms (68W25) Combinatorial optimization (90C27)

Recommendations

• Two for One: Tight Approximation of 2D Bin Packing
• New approximability results for two-dimensional bin packing
• Fast Approximation Schemes for Two-Stage, Two-Dimensional Bin Packing
• Improved approximation algorithm for two-dimensional bin packing
• New approximability results for two-dimensional bin packing

Cites work

• A 3-approximation algorithm for two-dimensional bin packing
• A algorithm for two-dimensional packing
• A near-optimal solution to a two-dimensional cutting stock problem
• A New Approximation Method for Set Covering Problems, with Applications to Multidimensional Bin Packing
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• Approximating the advertisement placement problem
• Bounds on Multiprocessing Timing Anomalies
• Hardness of approximation for orthogonal rectangle packing and covering problems
• Maximizing the total profit of rectangles packed into a rectangle
• Orthogonal Packings in Two Dimensions
• Packing d-Dimensional Bins in d Stages
• Rectangle packing with one-dimensional resource augmentation

Cited in

(3)

• A 3/2-approximation for big two-bar charts packing
• Two for One: Tight Approximation of 2D Bin Packing
• A posteriori analysis of the algorithms for two-bar charts packing problem

This page was built for publication: Two for one: tight approximation of 2D bin packing

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