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.529426/17≈1.5294 improving the best known algorithm by Kellerer and Kotov (2013) with a stretching factor 11/7≈1.571411/7≈1.5714. Our algorithm has 2 stages and uses bunch techniques: we aggregate bins into batches sharing a common purpose.
Origin | Files produced by the author(s) |
---|
Loading...