{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,17]],"date-time":"2026-01-17T11:10:29Z","timestamp":1768648229552,"version":"3.49.0"},"reference-count":5,"publisher":"Springer Science and Business Media LLC","issue":"8","license":[{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T00:00:00Z","timestamp":1622764800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100009057","name":"Karl-Franzens-Universit\u00e4t Graz","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100009057","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Optim Lett"],"published-print":{"date-parts":[[2021,11]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We consider the product knapsack problem, which is the variant of the classical 0-1\u00a0knapsack problem where the objective consists of maximizing the product of the profits of the selected items. These profits are allowed to be positive or negative. We present the first fully polynomial-time approximation scheme for the product knapsack problem, which is known to be weakly -hard. Moreover, we analyze the approximation quality achieved by a natural extension of the classical knapsack greedy procedure to the product knapsack problem.<\/jats:p>","DOI":"10.1007\/s11590-021-01760-x","type":"journal-article","created":{"date-parts":[[2021,6,4]],"date-time":"2021-06-04T21:03:27Z","timestamp":1622840607000},"page":"2529-2540","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Approximating the product knapsack problem"],"prefix":"10.1007","volume":"15","author":[{"given":"Ulrich","family":"Pferschy","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Schauer","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0897-3571","authenticated-orcid":false,"given":"Clemens","family":"Thielen","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,6,4]]},"reference":[{"issue":"4","key":"1760_CR1","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1007\/s11590-017-1227-5","volume":"12","author":"C D\u2019Ambrosio","year":"2018","unstructured":"D\u2019Ambrosio, C., Furini, F., Monaci, M., Traversi, E.: On the product knapsack problem. Optim. Lett. 12(4), 691\u2013712 (2018)","journal-title":"Optim. Lett."},{"key":"1760_CR2","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1007\/s00291-018-0543-1","volume":"41","author":"N Halman","year":"2019","unstructured":"Halman, N., Kovalyov, M., Quilliot, A., Shabtay, D., Zofi, M.: Bi-criteria path problem with minimum length and maximum survival probability. OR Spectr. 41, 469\u2013489 (2019)","journal-title":"OR Spectr."},{"key":"1760_CR3","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.: Knapsack Problems. Springer, Berlin (2004)"},{"key":"1760_CR4","volume-title":"Knapsack problems: Algorithms and computer implementations","author":"S Martello","year":"1990","unstructured":"Martello, S., Toth, P.: Knapsack problems: Algorithms and computer implementations. Wiley, New Jersey (1990)"},{"key":"1760_CR5","unstructured":"Pferschy, U., Schauer, J., Thielen, C.: The product knapsack problem: Approximation and complexity. arXiv: 1901.00695. (2019)"}],"container-title":["Optimization Letters"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01760-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11590-021-01760-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11590-021-01760-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,9,24]],"date-time":"2021-09-24T01:32:44Z","timestamp":1632447164000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11590-021-01760-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,6,4]]},"references-count":5,"journal-issue":{"issue":"8","published-print":{"date-parts":[[2021,11]]}},"alternative-id":["1760"],"URL":"https:\/\/doi.org\/10.1007\/s11590-021-01760-x","relation":{},"ISSN":["1862-4472","1862-4480"],"issn-type":[{"value":"1862-4472","type":"print"},{"value":"1862-4480","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,6,4]]},"assertion":[{"value":"9 April 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 May 2021","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 June 2021","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that there is no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}]}}