Show simple item record

dc.contributor.authorD’Ambrosio, Claudia
dc.contributor.authorFurini, Fabio
dc.contributor.authorMonaci, Michele
dc.contributor.authorTraversi, Emiliano
dc.date.accessioned2019-04-12T14:11:23Z
dc.date.available2019-04-12T14:11:23Z
dc.date.issued2018
dc.identifier.issn1862-4480
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/18640
dc.language.isoenen
dc.subjectKnapsack problemen
dc.subjectDynamic programmingen
dc.subjectComplexityen
dc.subjectMixed integer (non)linear programmingen
dc.subject.ddc005en
dc.titleOn the Product Knapsack Problemen
dc.typeArticle accepté pour publication ou publié
dc.description.abstractenGiven a set of items, each characterized by a profit and a weight, we study the problem of maximizing the product of the profits of the selected items, while respecting a given capacity. To the best of our knowledge this is the first manuscript that studies this variant of the knapsack problem which we call Product Knapsack Problem (PKP). We show that PKP is weakly NP-hard. We propose and implement a Dynamic Programming algorithm and different Mixed Integer Linear and Nonlinear Programming formulations for the PKP. Finally, we present an extensive computational study on a large set of benchmark instances derived from the literature.en
dc.relation.isversionofjnlnameOptimization Letters
dc.relation.isversionofjnlvol12en
dc.relation.isversionofjnlissue4en
dc.relation.isversionofjnldate2018-06
dc.relation.isversionofjnlpages691-712en
dc.relation.isversionofdoi10.1007/s11590-017-1227-5en
dc.subject.ddclabelProgrammation, logiciels, organisation des donnéesen
dc.relation.forthcomingnonen
dc.relation.forthcomingprintnonen
dc.description.ssrncandidatenonen
dc.description.halcandidateouien
dc.description.readershiprechercheen
dc.description.audienceInternationalen
dc.relation.Isversionofjnlpeerreviewednonen
dc.relation.Isversionofjnlpeerreviewednonen
dc.date.updated2019-03-27T11:55:33Z
hal.person.labIds2071
hal.person.labIds989
hal.person.labIds461036
hal.person.labIds994
hal.identifierhal-02098406*


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