Two for One: Tight Approximation of 2D Bin Packing

DOI10.1007/978-3-642-03367-4_35MaRDI QIDQ3183471zbMATH OpenOpenAlexFDO

Authors Lars Prädel, Ulrich M. Schwarz, 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 algorithms (68W25) Combinatorial optimization (90C27) Approximation methods and heuristics in mathematical programming (90C59)

Recommendations

• Two for one: tight approximation of 2D bin packing
• New approximability results for two-dimensional bin packing
• New approximability results for two-dimensional bin packing
• Improved approximation algorithm for two-dimensional bin packing
• Bin Packing in Multiple Dimensions: Inapproximability Results and Approximation Schemes

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 Polynomial Time Approximation Scheme for the Square Packing Problem
• A Strip-Packing Algorithm with Absolute Performance Bound 2
• A structural lemma in 2-dimensional packing, and its implications on approximability
• Approximating the advertisement placement problem
• Bounds on Multiprocessing Timing Anomalies
• scientific article; zbMATH DE number 3888915 (Why is no real title available?)
• Maximizing the total profit of rectangles packed into a rectangle
• New approximability and inapproximability results for 2-dimensional bin packing
• New Approximability Results for 2-Dimensional Packing Problems
• On rectangle packing, maximizing benefits
• Orthogonal Packings in Two Dimensions
• Packing Rectangles into 2OPT Bins Using Rotations

Cited in

(13)

• Number of bins and maximum lateness minimization in two-dimensional bin packing
• A 3/2-approximation for big two-bar charts packing
• Approximation and online algorithms for multidimensional bin packing: a survey
• Two-dimensional bin packing with one-dimensional resource augmentation
• New approximability results for two-dimensional bin packing
• A structural lemma in 2-dimensional packing, and its implications on approximability
• A (5/3+)-approximation for strip packing
• A posteriori analysis of the algorithms for two-bar charts packing problem
• Two for one: tight approximation of 2D bin packing
• A quasi-PTAS for the two-dimensional geometric knapsack problem
• Improved approximation algorithm for two-dimensional bin packing
• New approximability results for two-dimensional bin packing
• Hybrid next-fit algorithm for the two-dimensional rectangle bin-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 Q3183471)