Artikel
On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem
In this article, we introduce the rectangular knapsack problem as a special case of the quadratic knapsack problem consisting in the maximization of the product of two separate knapsack profits subject to a cardinality constraint. We propose a polynomial time algorithm for this problem that provides a constant approximation ratio of 4.5. Our experimental results on a large number of artificially generated problem instances show that the average ratio is far from theoretical guarantee. In addition, we suggest refined versions of this approximation algorithm with the same time complexity and approximation ratio that lead to even better experimental results.
- Sprache
-
Englisch
- Erschienen in
-
Journal: Mathematical Methods of Operations Research ; ISSN: 1432-5217 ; Volume: 92 ; Year: 2020 ; Issue: 1 ; Pages: 107-132 ; Berlin, Heidelberg: Springer
- Klassifikation
-
Wirtschaft
- Thema
-
Quadratic knapsack problem
Approximation algorithm
Multiobjective combinatorial optimization
Hypervolume
- Ereignis
-
Geistige Schöpfung
- (wer)
-
Schulze, Britta
Stiglmayr, Michael
Paquete, Luís
Fonseca, Carlos M.
Willems, David
Ruzika, Stefan
- Ereignis
-
Veröffentlichung
- (wer)
-
Springer
- (wo)
-
Berlin, Heidelberg
- (wann)
-
2020
- DOI
-
doi:10.1007/s00186-020-00702-0
- 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
- Schulze, Britta
- Stiglmayr, Michael
- Paquete, Luís
- Fonseca, Carlos M.
- Willems, David
- Ruzika, Stefan
- Springer
Entstanden
- 2020
Ähnliche Objekte (12)
Parameterized approximation scheme for the multiple knapsack problem
A genetic algorithm for the twodimensional Knapsack problem with rectangular pieces
Algorithmen zum Knapsack-Problem
A fast approximation scheme for the multiple knapsack problem
Approximating the product knapsack problem
Knapsack problems : with 33 tables
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
"A.Y.H. Knapsack"
On a Cardinality Constrained Multicriteria Knapsack Problem
New Perspectives on Multi-Objective Knapsack Problems
Electronic commerce logistics and the knapsack problem
Pricing the multiple-choice nested knapsack problem
Parameterized approximation scheme for the multiple knapsack problem
A genetic algorithm for the twodimensional Knapsack problem with rectangular pieces
Algorithmen zum Knapsack-Problem
A fast approximation scheme for the multiple knapsack problem
Approximating the product knapsack problem
Knapsack problems : with 33 tables
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
"A.Y.H. Knapsack"
On a Cardinality Constrained Multicriteria Knapsack Problem
New Perspectives on Multi-Objective Knapsack Problems
Electronic commerce logistics and the knapsack problem
Pricing the multiple-choice nested knapsack problem
Parameterized approximation scheme for the multiple knapsack problem
A genetic algorithm for the twodimensional Knapsack problem with rectangular pieces
Algorithmen zum Knapsack-Problem
A fast approximation scheme for the multiple knapsack problem
Approximating the product knapsack problem
Knapsack problems : with 33 tables
Knapsack, Zweigpostamt Knapsack, Großgemeinde Hürth
"A.Y.H. Knapsack"
On a Cardinality Constrained Multicriteria Knapsack Problem
New Perspectives on Multi-Objective Knapsack Problems
Electronic commerce logistics and the knapsack problem