Publication at Faculty of Mathematics and Physics |
2016
Abstract
Online Bin Stretching is a semi-online variant of Bin Packing with a set number of m bins, where all bins can be overpacked to capacity S >= 1, which is to be minimized. There is also a guarantee that an offline algorithm can pack the input to m bins of unit size.
We focus on the problem of Online Bin Stretching for small m, namely 3 <= m <= 5. Recent progress on this problem has led into a lower bound of 19/14 ~ 1.357 for m = 3 and an upper bound of 11/8 ~ 1.375 for the same.
For m = 4 and m = 5, only a trivial lower bound of 4/3 was known. We improve the techniques used in the previous lower bound for m = 3 to reach a lower bound of 45/33 ~ 1.36 for m=3 and a new lower bound of 19/14 ~ 1.357 for m = 4 and m = 5.