• 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

Bridging gap between standard and differential polynomial approximation: the case of bin-packing

Thumbnail
Date
1999
Dewey
Recherche opérationnelle
Sujet
Bin-packing; Polynomial approximation
Journal issue
Applied Mathematics Letters
Volume
12
Number
7
Publication date
10-1999
Article pages
127-133
Publisher
Elsevier
DOI
http://dx.doi.org/10.1016/S0893-9659(99)00112-3
URI
https://basepub.dauphine.fr/handle/123456789/3690
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Demange, Marc
Monnot, Jérôme
Paschos, Vangelis
Type
Article accepté pour publication ou publié
Abstract (EN)
The purpose of this paper is mainly to prove the following theorem: for every polynomial time algorithm running in time T(n) and guaranteeing standard-approximation ratio varrho for bin-packing, there exists an algorithm running in time O(nT(n)) and achieving differential-approximation ratio 2 − varrho for BP. This theorem has two main impacts. The first one is “operational”, deriving a polynomial time differential-approximation schema for bin-packing. The second one is structural, establishing a kind of reduction (to our knowledge not existing until now) between standard approximation and differential one.

  • 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.