Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorMonnot, Jérôme
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-03-15T13:42:37Z
dc.date.available2010-03-15T13:42:37Z
dc.date.issued1999
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3690
dc.language.isoenen
dc.subjectBin-packingen
dc.subjectPolynomial approximationen
dc.subject.ddc003en
dc.titleBridging gap between standard and differential polynomial approximation: the case of bin-packingen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenThe 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.isversionofjnlnameApplied Mathematics Letters
dc.relation.isversionofjnlvol12en
dc.relation.isversionofjnlissue7en
dc.relation.isversionofjnldate1999-10
dc.relation.isversionofjnlpages127-133en
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/S0893-9659(99)00112-3en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherElsevieren
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

FilesSizeFormatView

There are no files associated with this item.

This item appears in the following Collection(s)

Show simple item record