Online bin stretching with bunch techniques

Abstract

We are given a sequence of items that can be packed into m unit size bins and the goal is to assign these items online to m bins while minimizing the stretching factor. Bins have infinite capacities and the stretching factor is the size of the largest bin. We present an algorithm with stretching factor 26/17 ≈ 1.5294 improving the best known algorithm by Kellerer and Kotov (2013) [1] with a stretching factor 11/7 ≈ 1.5714. Our algorithm has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose. © 2015 Elsevier B.V.