On-line bin-stretching

Yossi Azar, Oded Regev

Research output: Contribution to journalConference articlepeer-review

Abstract

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number m of bins. We then combine the two algorithms and design an algorithm whose stretching factor is 1.625 for any m. The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is 4/3 for any m≥2. We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the value of the makespan (maximum load) is known in advance.

Original languageEnglish (US)
Pages (from-to)17-41
Number of pages25
JournalTheoretical Computer Science
Volume268
Issue number1
DOIs
StatePublished - Oct 6 2001
EventOn-line Algorithms'98 (OLA'98) - Udine, Italy
Duration: Aug 31 1998Sep 5 1998

Keywords

  • Approximation algorithms
  • Bin stretching
  • Bin-packing
  • Load balancing
  • On-line algorithms
  • Scheduling

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On-line bin-stretching'. Together they form a unique fingerprint.

Cite this