On-line bin-stretching

Yossi Azar, Oded Regev

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we x 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 x 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)
Title of host publicationRandomization and Approximation Techniques in Computer Science - 2nd International Workshop, RANDOM 1998, Proceedings
EditorsMaria Serna, José D.P Rolim, Michael Luby
PublisherSpringer Verlag
Pages71-81
Number of pages11
ISBN (Print)354065142X, 9783540651420
DOIs
StatePublished - 1998
Event2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998 - Barcelona, Spain
Duration: Oct 8 1998Oct 10 1998

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume1518
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other2nd International Workshop on Randomization and Approximation Techniques in Computer Science, Random 1998
CountrySpain
CityBarcelona
Period10/8/9810/10/98

Keywords

  • Approximation algorithms
  • Bin-packing
  • Bin-stretching
  • 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