Bitte verwenden Sie diesen Link, um diese Publikation zu zitieren, oder auf sie als Internetquelle zu verweisen: https://hdl.handle.net/10419/307079 
Erscheinungsjahr: 
2022
Quellenangabe: 
[Journal:] Mathematical Methods of Operations Research [ISSN:] 1432-5217 [Volume:] 96 [Issue:] 1 [Publisher:] Springer [Place:] Berlin, Heidelberg [Year:] 2022 [Pages:] 149-160
Verlag: 
Springer, Berlin, Heidelberg
Zusammenfassung: 
A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107–132, 2020) presented the Rectangular Knapsack Problem ( Rkp ) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem ( Cbkp ). To this end, they started an investigation into its complexity and approximability. The key results are an NP -hardness proof for a more general scenario than Rkp , and a 4.5-approximation for Rkp , raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) Rkp is indeed NP -hard in the considered setting (and even in more restricted settings), and (b) there exists both a pseudopolynomial algorithm and a fully-polynomial time approximation scheme (i.e., efficient approximability within any desired ratio α>1) for Rkp .
Schlagwörter: 
Quadratic optimization
Knapsack problems
Multiobjective optimization
Approximation
Persistent Identifier der Erstveröffentlichung: 
Creative-Commons-Lizenz: 
cc-by Logo
Dokumentart: 
Article
Dokumentversion: 
Published Version

Datei(en):
Datei
Größe





Publikationen in EconStor sind urheberrechtlich geschützt.