Approximating the product knapsack problem - Ulrich Pferschy; Joachim Schauer; Clemens Thielen (Optimization Letters, 2021)
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.
Keywords: 510; Knapsack problem; Approximation scheme; Greedy procedure