{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,27]],"date-time":"2025-08-27T16:35:07Z","timestamp":1756312507436,"version":"3.37.3"},"reference-count":13,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100016379","name":"Universit\u00e4t Osnabr\u00fcck","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100016379","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2022,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A recent paper by Schulze et al. (Math Methods Oper Res 92(1):107\u2013132, 2020) presented the Rectangular Knapsack Problem (<jats:sc>Rkp<\/jats:sc>) as a crucial subproblem in the study on the Cardinality-constrained Bi-objective Knapsack Problem (<jats:sc>Cbkp<\/jats:sc>). To this end, they started an investigation into its complexity and approximability. The key results are an  -hardness proof for a more general scenario than <jats:sc>Rkp<\/jats:sc>, and a 4.5-approximation for <jats:sc>Rkp<\/jats:sc>, raising the question of improvements for either result. In this note we settle both questions conclusively: we show that (a) <jats:sc>Rkp<\/jats:sc> is indeed  -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 <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\alpha &gt;1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b1<\/mml:mi>\n                    <mml:mo>&gt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>) for <jats:sc>Rkp<\/jats:sc>.\n<\/jats:p>","DOI":"10.1007\/s00186-022-00788-8","type":"journal-article","created":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T20:48:07Z","timestamp":1654807687000},"page":"149-160","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["On the rectangular knapsack problem"],"prefix":"10.1007","volume":"96","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7950-6965","authenticated-orcid":false,"given":"Fritz","family":"B\u00f6kler","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4681-5550","authenticated-orcid":false,"given":"Markus","family":"Chimani","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4593-8740","authenticated-orcid":false,"given":"Mirko H.","family":"Wagner","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,6,9]]},"reference":[{"issue":"12","key":"788_CR1","first-page":"1603","volume":"48","author":"T Erlebach","year":"2002","unstructured":"Erlebach T, Kellerer H, Pferschy U (2002) Approximating multiobjective knapsack problems. Manag Sci 48(12):1603\u20131612","journal-title":"Approximating multiobjective knapsack problems. Manag Sci"},{"key":"788_CR2","volume-title":"Combinatorial optimization, mathematical programming studies","author":"G Gallo","year":"1980","unstructured":"Gallo G, Hammer P, Simeone B (1980) Quadratic knapsack problems. In: Padberg M (ed) Combinatorial optimization, mathematical programming studies, vol 12. Springer, Berlin"},{"key":"788_CR3","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability; a guide to the theory of NP-completeness. Series of books in the mathematical sciences. W. H. Freeman & Co, New York"},{"issue":"4","key":"788_CR4","doi-asserted-by":"publisher","first-page":"769","DOI":"10.1007\/s00453-008-9248-1","volume":"57","author":"H Kellerer","year":"2010","unstructured":"Kellerer H, Strusevich VA (2010) Fully polynomial approximation schemes for a symmetric quadratic knapsack problem and its scheduling applications. Algorithmica 57(4):769\u2013795","journal-title":"Algorithmica"},{"issue":"9","key":"788_CR5","doi-asserted-by":"publisher","first-page":"494","DOI":"10.1287\/mnsc.15.9.494","volume":"15","author":"GL Nemhauser","year":"1969","unstructured":"Nemhauser GL, Ullmann Z (1969) Discrete dynamic programming and capital allocation. Manag Sci 15(9):494\u2013505","journal-title":"Manag Sci"},{"key":"788_CR6","unstructured":"Papadimitriou CH, Yannakakis M (2000) On the approximability of trade-offs and optimal access of web sources. In: FOCS. IEEE Computer Society, pp 86\u201392"},{"key":"788_CR7","doi-asserted-by":"publisher","DOI":"10.1016\/j.cor.2021.105349","volume":"137","author":"L Paquete","year":"2022","unstructured":"Paquete L, Schulze B, Stiglmayr M et al (2022) Computing representations with hypervolume scalarizations. Comput Oper Res 137:105349","journal-title":"Comput Oper Res"},{"issue":"2","key":"788_CR8","doi-asserted-by":"publisher","first-page":"308","DOI":"10.1287\/ijoc.2015.0678","volume":"28","author":"U Pferschy","year":"2016","unstructured":"Pferschy U, Schauer J (2016) Approximation of the quadratic knapsack problem. INFORMS J Comput 28(2):308\u2013318","journal-title":"INFORMS J Comput"},{"issue":"5","key":"788_CR9","doi-asserted-by":"publisher","first-page":"623","DOI":"10.1016\/j.dam.2006.08.007","volume":"155","author":"D Pisinger","year":"2007","unstructured":"Pisinger D (2007) The quadratic knapsack problem\u2013a survey. Discrete Appl Math 155(5):623\u2013648","journal-title":"Discrete Appl Math"},{"issue":"3","key":"788_CR10","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"DJJ Rader","year":"2002","unstructured":"Rader DJJ, Woeginger GJ (2002) The quadratic $$0-1$$ knapsack problem with series-parallel support. Oper Res Lett 30(3):159\u2013166","journal-title":"Oper Res Lett"},{"issue":"1","key":"788_CR11","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1007\/s00186-020-00702-0","volume":"92","author":"B Schulze","year":"2020","unstructured":"Schulze B, Stiglmayr M, Paquete L et al (2020) On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem. Math Methods Oper Res 92(1):107\u2013132","journal-title":"Math Methods Oper Res"},{"issue":"4","key":"788_CR12","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1016\/j.orl.2016.05.005","volume":"44","author":"R Taylor","year":"2016","unstructured":"Taylor R (2016) Approximation of the quadratic knapsack problem. Oper Res Lett 44(4):495\u2013497","journal-title":"Oper Res Lett"},{"issue":"2","key":"788_CR13","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.ejor.2011.10.049","volume":"218","author":"Z Xu","year":"2012","unstructured":"Xu Z (2012) A strongly polynomial FPTAS for the symmetric quadratic knapsack problem. Eur J Oper Res 218(2):377\u2013381","journal-title":"Eur J Oper Res"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-022-00788-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00186-022-00788-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-022-00788-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,10,5]],"date-time":"2022-10-05T18:22:33Z","timestamp":1664994153000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00186-022-00788-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":13,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,8]]}},"alternative-id":["788"],"URL":"https:\/\/doi.org\/10.1007\/s00186-022-00788-8","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"type":"print","value":"1432-2994"},{"type":"electronic","value":"1432-5217"}],"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"17 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"9 June 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}