Abstract
We study online bounded space bin packing in the resource augmentation model of competitive analysis. In this model, the online bounded space packing algorithm has to pack a list L of items in (0,1] into a small number of bins of size b≥1. Its performance is measured by comparing the produced packing against the optimal offline packing of the list L into bins of size 1.
We present a complete solution to this problem: For every bin size b≥1, we design online bounded space bin packing algorithms whose worst case ratio in this model comes arbitrarily close to a certain bound ρ(b). Moreover, we prove that no online bounded space algorithm can perform better than ρ(b) in the worst case.
| Original language | English |
|---|---|
| Pages (from-to) | 308-320 |
| Journal | Journal of algorithms |
| Volume | 44 |
| Issue number | 2 |
| DOIs | |
| Publication status | Published - 2002 |
| Event | 27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland Duration: 9 Jul 2000 → 15 Jul 2000 Conference number: 27 |
Keywords
- Asymptotic worst case ratio
- Competitive Analysis
- Bin packing
- Approximation Algorithm
- IR-74804
- METIS-208626
- On-line algorithm
- Resource augmentation