Improved Approximation Algorithm for Two-Dimensional Bin Packing

DOI10.1137/1.9781611973402.2zbMath1422.68290OpenAlexW4235135305MaRDI QIDQ5383961

Nikhil Bansal, Arindam Khan

Publication date: 20 June 2019

Published in: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/1.9781611973402.2

zbMATH Keywords

combinatorial optimizationapproximation algorithmsbin packingrectangle packingscheduling and resource allocation problems

Mathematics Subject Classification ID

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

Related Items (16)

Approximating Smallest Containers for Packing Three-Dimensional Convex Objects ⋮ Polynomial-time approximation schemes for circle and other packing problems ⋮ On the number of anchored rectangle packings for a planar point set ⋮ On the Number of Anchored Rectangle Packings for a Planar Point Set ⋮ Approximation and online algorithms for multidimensional bin packing: a survey ⋮ A tight \((3/2+\varepsilon)\)-approximation for skewed strip packing ⋮ Online circle and sphere packing ⋮ Tight approximation algorithms for geometric bin packing with skewed items ⋮ Peak demand minimization via sliced strip packing ⋮ On Guillotine Separability of Squares and Rectangles. ⋮ A Tight (3/2+ε) Approximation for Skewed Strip Packing. ⋮ Anchored rectangle and square packings ⋮ Online square-into-square packing ⋮ On the complexity of anchored rectangle packing ⋮ Closing the Gap for Pseudo-Polynomial Strip Packing ⋮ New approximability results for two-dimensional bin packing

This page was built for publication: Improved Approximation Algorithm for Two-Dimensional Bin Packing