Artikel
Approximating the product knapsack problem
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.
- Language
-
Englisch
- Bibliographic citation
-
Journal: Optimization Letters ; ISSN: 1862-4480 ; Volume: 15 ; Year: 2021 ; Issue: 8 ; Pages: 2529-2540 ; Berlin, Heidelberg: Springer
- Classification
-
Mathematik
- Subject
-
Knapsack problem
Approximation scheme
Greedy procedure
- Event
-
Geistige Schöpfung
- (who)
-
Pferschy, Ulrich
Schauer, Joachim
Thielen, Clemens
- Event
-
Veröffentlichung
- (who)
-
Springer
- (where)
-
Berlin, Heidelberg
- (when)
-
2021
- DOI
-
doi:10.1007/s11590-021-01760-x
- Last update
-
10.03.2025, 11:43 AM CET
Data provider
This object is provided by:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. If you have any questions about the object, please contact the data provider.
Object type
- Artikel
Associated
- Pferschy, Ulrich
- Schauer, Joachim
- Thielen, Clemens
- Springer
Time of origin
- 2021
Other Objects (12)
On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
The knapsack problem with special neighbor constraints
Revenue maximization in the dynamic knapsack problem
Approximating innovation potential with neurofuzzy robust model
A novel core-based optimization framework for binary integer programs- the multidemand multidimesional Knapsack problem as a test problem
Algorithmen zum Knapsack-Problem
Knapsack problems : with 33 tables
Tighter reformulations using classical Dawson and Sankoff bounds for approximating two-stage chance-constrained programs
Approximating Perpetuities
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
Approximating Data and Statistical Procedures - I. Approximating Data
Approximating data and statistical procedures. I. Approximating data
On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
The knapsack problem with special neighbor constraints
Revenue maximization in the dynamic knapsack problem
Approximating innovation potential with neurofuzzy robust model
A novel core-based optimization framework for binary integer programs- the multidemand multidimesional Knapsack problem as a test problem
Algorithmen zum Knapsack-Problem
Knapsack problems : with 33 tables
Tighter reformulations using classical Dawson and Sankoff bounds for approximating two-stage chance-constrained programs
Approximating Perpetuities
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
Approximating Data and Statistical Procedures - I. Approximating Data
Approximating data and statistical procedures. I. Approximating data
On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
The knapsack problem with special neighbor constraints
Revenue maximization in the dynamic knapsack problem
Approximating innovation potential with neurofuzzy robust model
A novel core-based optimization framework for binary integer programs- the multidemand multidimesional Knapsack problem as a test problem
Algorithmen zum Knapsack-Problem
Knapsack problems : with 33 tables
Tighter reformulations using classical Dawson and Sankoff bounds for approximating two-stage chance-constrained programs
Approximating Perpetuities
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
Approximating Data and Statistical Procedures - I. Approximating Data