Please use this identifier to cite or link to this item: https://hdl.handle.net/10419/288295 
Year of Publication: 
2020
Citation: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 92 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2020 [Pages:] 107-132
Publisher: 
Springer, Berlin, Heidelberg
Abstract: 
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.
Subjects: 
Quadratic knapsack problem
Approximation algorithm
Multiobjective combinatorial optimization
Hypervolume
Persistent Identifier of the first edition: 
Creative Commons License: 
cc-by Logo
Document Type: 
Article
Document Version: 
Published Version

Files in This Item:
File
Size





Items in EconStor are protected by copyright, with all rights reserved, unless otherwise indicated.