Show simple item record

dc.contributor.authorPaschos, Vangelis*
dc.contributor.authorMonnot, Jérôme*
dc.contributor.authorDemange, Marc*
dc.date.accessioned2010-04-16T08:09:24Z
dc.date.available2010-04-16T08:09:24Z
dc.date.issued2001
dc.identifier.issn0867-6356
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3976
dc.language.isoenen
dc.subjectUnused Bins
dc.subjectbin packing
dc.subjectapproximation algorithms
dc.subject.ddc003en
dc.titleMaximizing the number of unused bins
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenWe 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.
dc.relation.isversionofjnlnameFoundations of Computing and Decision Sciences
dc.relation.isversionofjnlvol26
dc.relation.isversionofjnlissue2
dc.relation.isversionofjnldate2001
dc.relation.isversionofjnlpages169-186
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherPublishing House of Poznan University of Technology
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2018-02-13T13:18:23Z
hal.person.labIds*
hal.person.labIds*
hal.person.labIds*


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