Show simple item record

Implementing an efficient fptas for the 0–1 multi-objective knapsack problem

dc.contributor.authorBazgan, Cristina
dc.contributor.authorHugot, Hadrien
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2010-04-12T12:56:29Z
dc.date.available2010-04-12T12:56:29Z
dc.date.issued2009
dc.identifier.issn0377-2217
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/3931
dc.language.isoenen
dc.subjectMulti-objective knapsack problem
dc.subjectDominance relations
dc.subjectDynamic programming
dc.subjectApproximation
dc.subjectCombinatorial optimization
dc.subject.ddc003en
dc.titleImplementing an efficient fptas for the 0–1 multi-objective knapsack problem
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenIn the present work, we are interested in the practical behavior of a new fully polynomial time approximation schemes (fptas) to solve the approximation version of the 0–1 multi-objective knapsack problem. The proposed methodology makes use of very general techniques (such as dominance relations in dynamic programming) and thus may be applicable in the implementation of fptas for other problems as well.Extensive numerical experiments on various types of instances in the bi and tri-objective cases establish that our method performs very well both in terms of CPU time and size of solved instances. We point out some reasons for the good practical performance of our algorithm. A comparison with an exact method and the fptas proposed in [Erlebach, T., Kellerer, H., Pferschy, U., 2002. Approximating multiobjective knapsack problems. Management Science 48 (12), 1603–1612] is also performed.
dc.relation.isversionofjnlnameEuropean Journal of Operational Research
dc.relation.isversionofjnlvol198
dc.relation.isversionofjnlissue1
dc.relation.isversionofjnldate2009
dc.relation.isversionofjnlpages47-56
dc.relation.isversionofdoihttp://dx.doi.org/10.1016/j.ejor.2008.07.047
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.relation.Isversionofjnlpeerreviewedoui
dc.date.updated2016-10-06T09:44:43Z


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