• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

Maximizing the number of unused bins

Thumbnail
Date
2001
Dewey
Recherche opérationnelle
Sujet
Unused Bins; bin packing; approximation algorithms
Journal issue
Foundations of Computing and Decision Sciences
Volume
26
Number
2
Publication date
2001
Article pages
169-186
Publisher
Publishing House of Poznan University of Technology
URI
https://basepub.dauphine.fr/handle/123456789/3976
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Paschos, Vangelis
Monnot, Jérôme
Demange, Marc
Type
Article accepté pour publication ou publié
Abstract (EN)
We analyze the approximation behavior of some of the best-known polynomial-time approximation algorithms for bin-packing under an approximation criterion, called differential ratio, informally the ratio (n — where n is the size of the input list, is the size of the solution provided by an approximation algorithm and Beta(I) is the size of the optimal one. This measure has originally been introduced by Ausiello, D'Atri and Protasi and more recently revisited, in a more systematic way, by the first and the third authors of the present paper. Under the differential ratio, bin-packing has a natural formulation as the problem of maximizing the number of unused bins. We first show that two basic fit bin-packing algorithms, the first-fit and the best-fit, admit differential approximation ratios 1/2. Next, we show that slightly improved versions of them achieve ratios 2/3. Refining our analysis we show that the famous first-fit-decreasing and best-fit decreasing algorithms achieve differential approximation ratio 3/4: Finally, we show that first-fit-decreasing achieves asymptotic differential approximation ratio 7/9.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.