Improved approximation algorithm for two-dimensional bin packing

N. Bansal, A. Khan

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

31 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelProceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Portland OR, USA, January 5-7, 2014)
RedacteurenC. Chekuri
Plaats van productiePhiladelphia PA
UitgeverijSociety for Industrial and Applied Mathematics (SIAM)
Pagina's13-25
ISBN van geprinte versie978-1-61197-338-9
DOI's
StatusGepubliceerd - 2014
Evenement25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014) - Hilton Portland & Executive Tower, Portland, Verenigde Staten van Amerika
Duur: 5 jan 20147 jan 2014
Congresnummer: 25
https://www.siam.org/meetings/da14/

Congres

Congres25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2014)
Verkorte titelSODA '14
LandVerenigde Staten van Amerika
StadPortland
Periode5/01/147/01/14
Ander25th Annual ACM-SIAM Symposium on Discrete Algorithms
Internet adres

Vingerafdruk Duik in de onderzoeksthema's van 'Improved approximation algorithm for two-dimensional bin packing'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Bansal, N., & Khan, A. (2014). Improved approximation algorithm for two-dimensional bin packing. In C. Chekuri (editor), Proceedings 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'14, Portland OR, USA, January 5-7, 2014) (blz. 13-25). Society for Industrial and Applied Mathematics (SIAM). https://doi.org/10.1137/1.9781611973402.2