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.
- Sprache
-
Englisch
- Erschienen in
-
Journal: Optimization Letters ; ISSN: 1862-4480 ; Volume: 15 ; Year: 2021 ; Issue: 8 ; Pages: 2529-2540 ; Berlin, Heidelberg: Springer
- Klassifikation
-
Mathematik
- Thema
-
Knapsack problem
Approximation scheme
Greedy procedure
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Pferschy, Ulrich
Schauer, Joachim
Thielen, Clemens
- Ereignis
-
Veröffentlichung
- (wer)
-
Springer
- (wo)
-
Berlin, Heidelberg
- (wann)
-
2021
- DOI
-
doi:10.1007/s11590-021-01760-x
- Letzte Aktualisierung
-
10.03.2025, 11:43 MEZ
Datenpartner
Dieses Objekt wird bereitgestellt von:
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
ZBW - Deutsche Zentralbibliothek für Wirtschaftswissenschaften - Leibniz-Informationszentrum Wirtschaft. Bei Fragen zum Objekt wenden Sie sich bitte an den Datenpartner.
Objekttyp
- Artikel
Beteiligte
- Pferschy, Ulrich
- Schauer, Joachim
- Thielen, Clemens
- Springer
Entstanden
- 2021
Ähnliche Objekte (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