Resource augmentation in online bounded space bin packing

János Csirik, Gerhard Woeginger

Research output: Contribution to journalArticleAcademicpeer-review

22 Citations (Scopus)

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

Fingerprint Dive into the research topics of 'Resource augmentation in online bounded space bin packing'. Together they form a unique fingerprint.

Cite this