• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Maximizing the number of unused bins

Paschos, Vangelis; Monnot, Jérôme; Demange, Marc (2001), Maximizing the number of unused bins, Foundations of Computing and Decision Sciences, 26, 2, p. 169-186

Type
Article accepté pour publication ou publié
Date
2001
Journal name
Foundations of Computing and Decision Sciences
Volume
26
Number
2
Publisher
Publishing House of Poznan University of Technology
Pages
169-186
Metadata
Show full item record
Author(s)
Paschos, Vangelis

Monnot, Jérôme cc

Demange, Marc
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.
Subjects / Keywords
Unused Bins; bin packing; approximation algorithms

Related items

Showing items related by title and author.

  • Thumbnail
    Bridging gap between standard and differential polynomial approximation: the case of bin-packing 
    Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (1999) Article accepté pour publication ou publié
  • Thumbnail
    The hypocoloring problem: complexity and approximability results when the chromatic number is small 
    de Werra, Dominique; Demange, Marc; Monnot, Jérôme; Paschos, Vangelis (2004) Communication / Conférence
  • Thumbnail
    Differential approximation results for the Steiner tree problem 
    Monnot, Jérôme; Demange, Marc; Paschos, Vangelis (2003) Article accepté pour publication ou publié
  • Thumbnail
    Complexity and approximation results for the min weighted node coloring problem 
    Escoffier, Bruno; Demange, Marc; Paschos, Vangelis; de Werra, Dominique; Monnot, Jérôme (2008) Chapitre d'ouvrage
  • Thumbnail
    Time slot scheduling of compatible jobs 
    Demange, Marc; de Werra, Dominique; Monnot, Jérôme; Paschos, Vangelis (2007) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo