Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/287323 
Erscheinungsjahr: 
2021
Quellenangabe: 
[Journal:] Optimization Letters [ISSN:] 1862-4480 [Volume:] 15 [Issue:] 8 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2021 [Pages:] 2529-2540
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
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.
Schlagwörter: 
Knapsack problem
Approximation scheme
Greedy procedure
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.