online-2d-bin-packing.pdf (685.68 kB)
Bin packing in multiple dimensions
journal contributionposted on 2016-04-27, 13:54 authored by Rob van Stee
I mentioned in a previous column  that the best known lower bound for the two-dimensional online bin packing problem is 1.907 by Blitz, van Vliet, Woeginger , which is an unpublished (and now lost ) manuscript. I have realized since then that even the penultimate result, 1.856, was published only in Andre van Vliet's Ph.D. thesis  and is not readily available. It therefore seems like a good idea to describe his methods here, though not in full detail. This will include a discussion of the three-dimensional case. I will also survey other results in multidimensional packing, that were left out in my previous column.
CitationSIGACT News Online Algorithms Column 26: 2015, 46 (2), pp. 105-112
Author affiliation/Organisation/COLLEGE OF SCIENCE AND ENGINEERING/Department of Computer Science
- AM (Accepted Manuscript)