Journal
OPTIMIZATION LETTERS
Volume 15, Issue 8, Pages 2529-2540Publisher
SPRINGER HEIDELBERG
DOI: 10.1007/s11590-021-01760-x
Keywords
Knapsack problem; Approximation scheme; Greedy procedure
Funding
- Field of Excellence COLIBRI at the University of Graz
Ask authors/readers for more resources
The paper investigates the product knapsack problem and introduces the first fully polynomial-time approximation scheme for this problem, which is known to be weakly NP-hard. Additionally, the approximation quality achieved by extending the classical knapsack greedy procedure to the product knapsack problem is analyzed.
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.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available
Share Paper
