| dc.contributor.author | Demange, Marc | |
| dc.contributor.author | Monnot, Jérôme | |
| dc.contributor.author | Paschos, Vangelis | |
| dc.date.accessioned | 2010-03-15T13:42:37Z | |
| dc.date.available | 2010-03-15T13:42:37Z | |
| dc.date.issued | 1999 | |
| dc.identifier.uri | https://basepub.dauphine.fr/handle/123456789/3690 | |
| dc.language.iso | en | en |
| dc.subject | Bin-packing | en |
| dc.subject | Polynomial approximation | en |
| dc.subject.ddc | 003 | en |
| dc.title | Bridging gap between standard and differential polynomial approximation: the case of bin-packing | en |
| dc.type | Article accepté pour publication ou publié | |
| dc.description.abstracten | 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. | en |
| dc.relation.isversionofjnlname | Applied Mathematics Letters | |
| dc.relation.isversionofjnlvol | 12 | en |
| dc.relation.isversionofjnlissue | 7 | en |
| dc.relation.isversionofjnldate | 1999-10 | |
| dc.relation.isversionofjnlpages | 127-133 | en |
| dc.relation.isversionofdoi | http://dx.doi.org/10.1016/S0893-9659(99)00112-3 | en |
| dc.description.sponsorshipprivate | oui | en |
| dc.relation.isversionofjnlpublisher | Elsevier | en |
| dc.subject.ddclabel | Recherche opérationnelle | en |
