Improved approximation algorithm for two-dimensional bin packing

N. Bansal, A. Khan

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

33 Citations (Scopus)

Abstract

We study the two-dimensional bin packing problem with and without rotations. Here we are given a set of two-dimensional rectangular items I and the goal is to pack these into a minimum number of unit square bins. We consider the orthogonal packing case where the edges of the items must be aligned parallel to the edges of the bin. Our main result is a 1.405-approximation for two-dimensional bin packing with and without rotation, which improves upon a recent 1.5 approximation due to Jansen and Prädel. We also show that a wide class of rounding based algorithms cannot improve upon the factor of 1.5.
Original languageEnglish
Title of host publicationProceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Portland OR, USA, January 5-7, 2014)
EditorsC. Chekuri
Place of PublicationPhiladelphia PA
PublisherSociety for Industrial and Applied Mathematics (SIAM)
Pages13-25
ISBN (Print)978-1-61197-338-9
DOIs
Publication statusPublished - 2014
Event25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) - Hilton Portland & Executive Tower, Portland, United States
Duration: 5 Jan 20147 Jan 2014
Conference number: 25
https://www.siam.org/meetings/da14/

Conference

Conference25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
Abbreviated titleSODA '14
CountryUnited States
CityPortland
Period5/01/147/01/14
Internet address

Fingerprint Dive into the research topics of 'Improved approximation algorithm for two-dimensional bin packing'. Together they form a unique fingerprint.

Cite this