Resource augmentation in online bounded space bin packing

János Csirik, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)
4 Downloads (Pure)


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 languageEnglish
Pages (from-to)308-320
JournalJournal of algorithms
Issue number2
Publication statusPublished - 2002
Event27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Switzerland
Duration: 9 Jul 200015 Jul 2000
Conference number: 27


  • Asymptotic worst case ratio
  • Competitive Analysis
  • Bin packing
  • Approximation Algorithm
  • IR-74804
  • METIS-208626
  • On-line algorithm
  • Resource augmentation

Cite this