Probabilistic Analysis of Online (Class-Constrained) Bin Packing and Bin Covering
| Autor: | Carsten Fischer, Heiko Röglin |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Conjecture Bin packing problem Computer science Probabilistic logic 0102 computer and information sciences 01 natural sciences Bin 03 medical and health sciences 0302 clinical medicine 010201 computation theory & mathematics Simple (abstract algebra) 030220 oncology & carcinogenesis Probabilistic analysis of algorithms Online algorithm Greedy algorithm |
| Zdroj: | LATIN 2018: Theoretical Informatics ISBN: 9783319774039 LATIN |
| DOI: | 10.1007/978-3-319-77404-6_34 |
| Popis: | We study online algorithms for bin packing and bin covering in two different probabilistic settings in which the item sizes are drawn randomly or the items are adversarial but arrive in random order. We prove several results on the expected performance of well-known online algorithms in these settings. In particular, we prove that the simple greedy algorithm Dual Next-Fit for bin covering performs in the random-order setting strictly better than in the worst case, proving a conjecture by Christ et al. (Theoret Comput Sci 556:71–84, 2014). |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|