Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/287323 
Year of Publication: 
2021
Citation: 
[Journal:] Optimization Letters [ISSN:] 1862-4480 [Volume:] 15 [Issue:] 8 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2021 [Pages:] 2529-2540
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
We consider the product knapsack problem, which is the variant of the classical 0-1 knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly NP-hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.
Subjects: 
Knapsack problem
Approximation scheme
Greedy procedure
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.