On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem

Britta Schulze (), Michael Stiglmayr, Luís Paquete, Carlos M. Fonseca, David Willems and Stefan Ruzika
Additional contact information
Britta Schulze: University of Wuppertal
Michael Stiglmayr: University of Wuppertal
Luís Paquete: University of Coimbra
Carlos M. Fonseca: University of Coimbra
David Willems: University of Koblenz-Landau
Stefan Ruzika: University of Kaiserslautern

Mathematical Methods of Operations Research, 2020, vol. 92, issue 1, No 4, 107-132

Abstract: 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.

Keywords: Quadratic knapsack problem; Approximation algorithm; Multiobjective combinatorial optimization; Hypervolume (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s00186-020-00702-0 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:mathme:v:92:y:2020:i:1:d:10.1007_s00186-020-00702-0

Ordering information: This journal article can be ordered from
http://www.springer.com/economics/journal/00186

DOI: 10.1007/s00186-020-00702-0

Access Statistics for this article

Mathematical Methods of Operations Research is currently edited by Oliver Stein

More articles in Mathematical Methods of Operations Research from Springer, Gesellschaft für Operations Research (GOR), Nederlands Genootschap voor Besliskunde (NGB)
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().