| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 1142774 | Operations Research Letters | 2013 | 6 Pages |
Abstract
We consider online bin packing where in addition to the opening cost of each bin, the arriving items collect delay costs until their assigned bins are released (closed), and the open bins themselves collect holding costs. Besides being of practical interest, this problem generalises several previously unrelated online optimisation problems. We provide a general online algorithm for this problem with competitive ratio 7, with improvements for the special cases of zero delay or holding costs and size-proportional item delay costs.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Lauri Ahlroth, André Schumacher, Pekka Orponen,