Online Bin Covering: Expectations vs. Guarantees

Marie Gabriele Christ, Lene Monrad Favrholdt, Kim Skak Larsen

Publikation: Kapitel i bog/rapport/konference-proceedingKonferencebidrag i proceedingsForskningpeer review

Abstrakt

Bin covering is a dual version of classic bin packing. As usual, bins have size one and items with sizes between zero and one must be packed. However, in bin covering, the objective is to cover as many bins as possible, where a bin is covered if the sizes of items placed in the bin sum up to at least one. We are considering the online version of bin covering. Two classic algorithms for online bin packing that have natural dual versions are Harmonic k and Next-Fit. Though these two algorithms are quite different in nature, competitive analysis does not distinguish these bin covering algorithms.

In order to understand the combinatorial structure of the algorithms better, we turn to other performance measures, namely relative worst order, random order, and max/max analysis, as well as analyses under restricted input assumptions or uniformly distributed input. In this way, our study also supplements the ongoing systematic studies of the relative strengths of various performance measures.

We make the case that when guarantees are needed, even under restricted input sequences, the dual Harmonic k algorithm is preferable. In addition, we establish quite robust theoretical results showing that if items come from a uniform distribution or even if just the ordering of items is uniformly random, then dual Next-Fit is the right choice.
OriginalsprogEngelsk
TitelCombinatorial Optimization and Applications : 7th International Conference, COCOA 2013, Chengdu, China, December 12-14, 2013, Proceedings
RedaktørerPeter Widmayer, Yinfeng Xu, Binhai Zhu
Antal sider12
ForlagSpringer
Publikationsdato2013
Sider226-237
ISBN (Trykt)978-3-319-03779-0
ISBN (Elektronisk)978-3-319-03780-6
DOI
StatusUdgivet - 2013
Begivenhed7th International Conference on Combinatorial Optimization and Applications - Chengdu, Kina
Varighed: 12. dec. 201314. dec. 2013

Konference

Konference7th International Conference on Combinatorial Optimization and Applications
LandKina
ByChengdu
Periode12/12/201314/12/2013
NavnLecture Notes in Computer Science
Vol/bind8287
ISSN0302-9743

Fingeraftryk Dyk ned i forskningsemnerne om 'Online Bin Covering: Expectations vs. Guarantees'. Sammen danner de et unikt fingeraftryk.

  • Citationsformater

    Christ, M. G., Favrholdt, L. M., & Larsen, K. S. (2013). Online Bin Covering: Expectations vs. Guarantees. I P. Widmayer, Y. Xu, & B. Zhu (red.), Combinatorial Optimization and Applications: 7th International Conference, COCOA 2013, Chengdu, China, December 12-14, 2013, Proceedings (s. 226-237). Springer. Lecture Notes in Computer Science, Bind. 8287 https://doi.org/10.1007/978-3-319-03780-6_20