Show simple item record

dc.contributor.authorBazgan, Cristina
dc.contributor.authorHugot, Hadrien
dc.contributor.authorVanderpooten, Daniel
dc.date.accessioned2011-04-05T08:53:04Z
dc.date.available2011-04-05T08:53:04Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/5900
dc.language.isoenen
dc.subjectMulti-objective knapsack problem
dc.subjectdynamic programming
dc.subjectcombinatorial optimization
dc.subjectdominance relations
dc.subjectapproximation
dc.subject.ddc003en
dc.titleA practical efficient fptas for the 0-1 multi-objective knapsack problem
dc.typeCommunication / Conférence
dc.description.abstractenIn the present work, we are interested in the practical behavior of a new fptas to solve the approximation version of the 0-1 multi-objective knapsack problem. Nevertheless, our methodology focuses on 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 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 is also performed.
dc.identifier.citationpages717-728
dc.relation.ispartoftitleAlgorithms - ESA 2007 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings
dc.relation.ispartofeditorWelzl, Emo
dc.relation.ispartofpublnameSpringer
dc.relation.ispartofpublcityBerlin Heidelberg
dc.relation.ispartofdate2007
dc.description.sponsorshipprivateouien
dc.subject.ddclabelRecherche opérationnelleen
dc.relation.ispartofisbn978-3-540-75519-7
dc.relation.confcountryISRAEL
dc.description.ssrncandidatenon
dc.description.halcandidateoui
dc.description.readershiprecherche
dc.description.audienceInternational
dc.date.updated2017-01-05T15:29:47Z


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record