{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,1]],"date-time":"2026-05-01T01:05:55Z","timestamp":1777597555636,"version":"3.51.4"},"reference-count":24,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T00:00:00Z","timestamp":1581465600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001655","name":"Deutscher Akademischer Austauschdienst","doi-asserted-by":"publisher","award":["57128839"],"award-info":[{"award-number":["57128839"]}],"id":[{"id":"10.13039\/501100001655","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Funda\u00e7\u00e3o para a Ci\u00eancia e Tecnologia"},{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["RU 1524\/4-1"],"award-info":[{"award-number":["RU 1524\/4-1"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math Meth Oper Res"],"published-print":{"date-parts":[[2020,8]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In this article, we introduce the <jats:italic>rectangular knapsack problem<\/jats:italic> 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.<\/jats:p>","DOI":"10.1007\/s00186-020-00702-0","type":"journal-article","created":{"date-parts":[[2020,2,12]],"date-time":"2020-02-12T08:03:22Z","timestamp":1581494602000},"page":"107-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem"],"prefix":"10.1007","volume":"92","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8528-3331","authenticated-orcid":false,"given":"Britta","family":"Schulze","sequence":"first","affiliation":[]},{"given":"Michael","family":"Stiglmayr","sequence":"additional","affiliation":[]},{"given":"Lu\u00eds","family":"Paquete","sequence":"additional","affiliation":[]},{"given":"Carlos M.","family":"Fonseca","sequence":"additional","affiliation":[]},{"given":"David","family":"Willems","sequence":"additional","affiliation":[]},{"given":"Stefan","family":"Ruzika","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2020,2,12]]},"reference":[{"issue":"2","key":"702_CR1","doi-asserted-by":"publisher","first-page":"310","DOI":"10.1016\/0377-2217(94)00229-0","volume":"92","author":"A Billionnet","year":"1996","unstructured":"Billionnet A, Calmels F (1996) Linear programming for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 92(2):310\u2013325","journal-title":"Eur J Oper Res"},{"key":"702_CR2","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/S0377-2217(03)00244-3","volume":"157","author":"A Billionnet","year":"2004","unstructured":"Billionnet A, Soutif E (2004) An exact method based on Lagrangian decomposition for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 157:565\u2013575","journal-title":"Eur J Oper Res"},{"key":"702_CR3","doi-asserted-by":"publisher","first-page":"664","DOI":"10.1016\/S0377-2217(97)00414-1","volume":"112","author":"A Billionnet","year":"1999","unstructured":"Billionnet A, Faye A, Soutif E (1999) A new upper bound for the 0\u20131 quadratic knapsack problem. Eur J Oper Res 112:664\u2013672","journal-title":"Eur J Oper Res"},{"key":"702_CR4","doi-asserted-by":"crossref","unstructured":"Burkard R, \u00c7ela E, Pardalos P, Pitsoulis L (1998) The quadratic assignment problem. In: Handbook of combinatorial optimization, vol 3","DOI":"10.1007\/978-1-4613-0303-9_27"},{"issue":"2","key":"702_CR5","doi-asserted-by":"publisher","first-page":"125","DOI":"10.1287\/ijoc.11.2.125","volume":"11","author":"A Caprara","year":"1999","unstructured":"Caprara A, Pisinger D, Toth P (1999) Exact solution of the quadratic knapsack problem. INFORMS J Comput 11(2):125\u2013137","journal-title":"INFORMS J Comput"},{"key":"702_CR6","volume-title":"Introduction to algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen TH, Leiserson CE, Rivest RL, Stein C (2001) Introduction to algorithms, 2nd edn. MIT Press, Cambridge","edition":"2"},{"key":"702_CR7","first-page":"132","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, pp 132\u2013149"},{"key":"702_CR8","volume-title":"Computers and intractability: a guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey MR, Johnson DS (1979) Computers and intractability: a guide to the theory of NP-completeness. W. H. Freeman and Company, New York"},{"issue":"2","key":"702_CR9","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1023\/A:1009898604624","volume":"4","author":"C Helmberg","year":"2000","unstructured":"Helmberg C, Rendl F, Weismantel R (2000) A semidefinite programming approach to the quadratic knapsack problem. J Comb Optim 4(2):197\u2013215","journal-title":"J Comb Optim"},{"issue":"1","key":"702_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1007\/BF01585164","volume":"62","author":"EL Johnson","year":"1993","unstructured":"Johnson EL, Mehrotra A, Nemhauser GL (1993) Min-cut clustering. Math Program 62(1):133\u2013151","journal-title":"Math Program"},{"issue":"4","key":"702_CR11","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"},{"key":"702_CR12","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24777-7","volume-title":"Knapsack problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer H, Pferschy U, Pisinger D (2004) Knapsack problems. Springer, Heidelberg"},{"key":"702_CR13","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1162\/EVCO_a_00157","volume":"24","author":"T Kuhn","year":"2016","unstructured":"Kuhn T, Fonseca CM, Paquete L, Ruzika S, Duarte MM, Figueira JR (2016) Hypervolume subset selection in two dimensions: formulations and algorithms. Evol Comput 24:411\u2013425","journal-title":"Evol Comput"},{"issue":"2","key":"702_CR14","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":"702_CR15","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\u2014a survey. Discrete Appl Math 155(5):623\u2013648","journal-title":"Discrete Appl Math"},{"key":"702_CR16","unstructured":"Pisinger D (2016) Exact algorithm for the quadratic knapsack problem and instance generator. http:\/\/www.diku.dk\/~pisinger\/codes.html"},{"issue":"2","key":"702_CR17","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1287\/ijoc.1050.0172","volume":"19","author":"DW Pisinger","year":"2007","unstructured":"Pisinger DW, Rasmussen AB, Sandvik R (2007) Solution of large quadratic knapsack problems through aggressive reduction. INFORMS J Comput 19(2):280\u2013290","journal-title":"INFORMS J Comput"},{"issue":"3","key":"702_CR18","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/S0167-6377(02)00122-0","volume":"30","author":"DJ Rader Jr","year":"2002","unstructured":"Rader DJ Jr, Woeginger GJ (2002) The quadratic 0\u20131 knapsack problem with series-parallel support. Oper Res Lett 30(3):159\u2013166","journal-title":"Oper Res Lett"},{"issue":"3","key":"702_CR19","doi-asserted-by":"publisher","first-page":"200","DOI":"10.1287\/mnsc.17.3.200","volume":"17","author":"JMW Rhys","year":"1970","unstructured":"Rhys JMW (1970) A selection problem of shared fixed costs and network flows. Manag Sci 17(3):200\u2013207","journal-title":"Manag Sci"},{"issue":"4","key":"702_CR20","doi-asserted-by":"publisher","first-page":"1449","DOI":"10.1137\/110820762","volume":"22","author":"CD Rodrigues","year":"2012","unstructured":"Rodrigues CD, Quadri D, Michelon P, Gueye S (2012) 0\u20131 quadratic knapsack problems: an exact approach based an a $$t$$-linearization. SIAM J Optim 22(4):1449\u20131468","journal-title":"SIAM J Optim"},{"issue":"4","key":"702_CR21","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"},{"key":"702_CR22","doi-asserted-by":"crossref","unstructured":"Witzgall C (1975) Mathematical models of site selection of electronic message systems (EMS). Washington, DC, Technical report, National Bureau of Standards","DOI":"10.6028\/NBS.IR.75-737"},{"issue":"2","key":"702_CR23","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"},{"key":"702_CR24","doi-asserted-by":"crossref","unstructured":"Zitzler E, Thiele L (1998) Multiobjective optimization using evolutionary algorithms\u2014a comparative case study. In: Eiben AE, B\u00e4ck T, Schoenauer M, Schwefel H-P (eds) Parallel problem solving from nature\u2014PPSN V. 5th International Conference Amsterdam, The Netherlands, 27\u201330 September 1998, Proceedings, volume 1498 of Lecture Notes in Computer Science. Springer, Berlin Heidelberg, pp 292\u2013301","DOI":"10.1007\/BFb0056872"}],"container-title":["Mathematical Methods of Operations Research"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00702-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00186-020-00702-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00186-020-00702-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,2,11]],"date-time":"2021-02-11T13:11:00Z","timestamp":1613049060000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00186-020-00702-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,12]]},"references-count":24,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,8]]}},"alternative-id":["702"],"URL":"https:\/\/doi.org\/10.1007\/s00186-020-00702-0","relation":{},"ISSN":["1432-2994","1432-5217"],"issn-type":[{"value":"1432-2994","type":"print"},{"value":"1432-5217","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,2,12]]},"assertion":[{"value":"16 January 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"7 January 2020","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"12 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}