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. |
Year | DOI | Venue |
---|---|---|
2013 | 10.1016/j.orl.2012.10.006 | Operations Research Letters |
Keywords | Field | DocType |
Competitive analysis,Online algorithm,Bin packing,Rent-to-buy | Online algorithm,Mathematical optimization,Bin,Holding cost,Bin packing problem,Mathematics,Competitive analysis | Journal |
Volume | Issue | ISSN |
41 | 1 | 0167-6377 |
Citations | PageRank | References |
1 | 0.37 | 12 |
Authors | ||
3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Lauri Ahlroth | 1 | 4 | 1.77 |
André Schumacher | 2 | 71 | 7.26 |
Pekka Orponen | 3 | 660 | 76.80 |