{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:42:57Z","timestamp":1740109377134,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T00:00:00Z","timestamp":1613174400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,2,13]],"date-time":"2021-02-13T00:00:00Z","timestamp":1613174400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"NWO","award":["Networks (NWO Gravitation grant)"],"award-info":[{"award-number":["Networks (NWO Gravitation grant)"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2021,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We discuss a game theoretic variant of the subset sum problem, in which two players compete for a common resource represented by a knapsack. Each player owns a private set of items, players pack items alternately, and each player either wants to maximize the total weight of his own items packed into the knapsack or to minimize the total weight of the items of the other player. We show that finding the best packing strategy against a hostile or a selfish adversary is PSPACE-complete, and that against these adversaries the optimal reachable item weight for a player cannot be approximated within any constant factor (unless P=NP). The game becomes easier when the adversary is short-sighted and plays greedily: finding the best packing strategy against a greedy adversary is NP-complete in the weak sense. This variant forms one of the rare examples of pseudo-polynomially solvable problems that have a PTAS, but do not allow an FPTAS (unless P=NP).<\/jats:p>","DOI":"10.1007\/s00224-021-10034-z","type":"journal-article","created":{"date-parts":[[2021,2,14]],"date-time":"2021-02-14T09:25:44Z","timestamp":1613294744000},"page":"884-900","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["The subset sum game revisited"],"prefix":"10.1007","volume":"65","author":[{"given":"Astrid","family":"Pieterse","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8816-2693","authenticated-orcid":false,"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,2,13]]},"reference":[{"key":"10034_CR1","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/j.orl.2009.01.007","volume":"37","author":"L Brotcorne","year":"2009","unstructured":"Brotcorne, L., Hanafi, S., Mansi, R.: A dynamic programming algorithm for the bilevel knapsack problem. Oper. Res. Lett. 37, 215\u2013218 (2009)","journal-title":"Oper. Res. Lett."},{"key":"10034_CR2","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130906593","volume":"24","author":"A Caprara","year":"2014","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: A complexity and approximability study of the bilevel knapsack problem. SIAM J. Optim. 24, 823\u2013838 (2014)","journal-title":"SIAM J. Optim."},{"key":"10034_CR3","doi-asserted-by":"publisher","first-page":"319","DOI":"10.1287\/ijoc.2015.0676","volume":"28","author":"A Caprara","year":"2016","unstructured":"Caprara, A., Carvalho, M., Lodi, A., Woeginger, G.J.: Bilevel knapsack with interdiction constraints. INFORMS J. Comput. 28, 319\u2013333 (2016)","journal-title":"INFORMS J. Comput."},{"key":"10034_CR4","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/j.orl.2017.12.009","volume":"46","author":"M Carvalho","year":"2018","unstructured":"Carvalho, M., Lodi, A., Marcotte, P.: A polynomial time algorithm for a continuous bilevel knapsack problem. Oper. Res. Lett. 46, 185\u2013188 (2018)","journal-title":"Oper. Res. Lett."},{"key":"10034_CR5","doi-asserted-by":"publisher","first-page":"539","DOI":"10.1016\/j.ejor.2013.08.047","volume":"233","author":"A Darmann","year":"2014","unstructured":"Darmann, A., Nicosia, G., Pferschy, U., Schauer, J.: The subset sum game. Eur. J. Oper. Res. 233, 539\u2013549 (2014)","journal-title":"Eur. J. Oper. Res."},{"key":"10034_CR6","first-page":"93","volume":"8","author":"S Dempe","year":"2000","unstructured":"Dempe, S., Richter, K.: Bilevel programming with Knapsack constraint. CEJOR 8, 93\u2013107 (2000)","journal-title":"CEJOR"},{"key":"10034_CR7","doi-asserted-by":"publisher","first-page":"784","DOI":"10.1016\/j.orl.2020.09.007","volume":"48","author":"D Fischer","year":"2020","unstructured":"Fischer, D., Woeginger, G.J.: A faster algorithm for the continuous bilevel knapsack problem. Oper. Res. Lett. 48, 784\u2013786 (2020)","journal-title":"Oper. Res. Lett."},{"key":"10034_CR8","volume-title":"Computers and intractability: A guide to the theory of NP-completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and intractability: A guide to the theory of NP-completeness. Freeman, San Francisco (1979)"},{"key":"10034_CR9","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1016\/j.tcs.2019.10.007","volume":"799","author":"G Nicosia","year":"2019","unstructured":"Nicosia, G., Pacifici, A., Pferschy, U.: A Stackelberg knapsack game with weight control. Theor. Comput. Sci. 799, 149\u2013159 (2019)","journal-title":"Theor. Comput. Sci."},{"key":"10034_CR10","doi-asserted-by":"publisher","first-page":"133","DOI":"10.1016\/j.endm.2018.07.018","volume":"69","author":"U Pferschy","year":"2018","unstructured":"Pferschy, U., Nicosia, G., Pacifici, A.: On a Stackelberg subset sum game. Electron Notes Discrete Math. 69, 133\u2013140 (2018)","journal-title":"Electron Notes Discrete Math."},{"key":"10034_CR11","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1016\/j.tcs.2015.06.027","volume":"595","author":"X Qiu","year":"2015","unstructured":"Qiu, X., Kern, W.: Improved approximation algorithms for a bilevel knapsack problem. Theor. Comput. Sci. 595, 120\u2013129 (2015)","journal-title":"Theor. Comput. Sci."},{"key":"10034_CR12","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0022-0000(78)90045-4","volume":"16","author":"TJ Schaefer","year":"1978","unstructured":"Schaefer, T.J.: On the complexity of some two-person perfect-information games. J. Comput. Syst. Sci. 16, 185\u2013225 (1978)","journal-title":"J. Comput. Syst. Sci."},{"key":"10034_CR13","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511921735","volume-title":"The design of approximation algorithms","author":"DP Williamson","year":"2011","unstructured":"Williamson, D.P., Shmoys, D.B.: The design of approximation algorithms. Cambridge University Press, Cambridge (2011)"},{"key":"10034_CR14","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1287\/ijoc.12.1.57.11901","volume":"12","author":"GJ Woeginger","year":"2000","unstructured":"Woeginger, G.J.: When does a dynamic programming formulation guarantee the existence of a fully polynomial time approximation scheme (FPTAS)? INFORMS J. Comput. 12, 57\u201375 (2000)","journal-title":"INFORMS J. Comput."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10034-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-021-10034-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-021-10034-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,6,28]],"date-time":"2021-06-28T03:22:01Z","timestamp":1624850521000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-021-10034-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,13]]},"references-count":14,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2021,7]]}},"alternative-id":["10034"],"URL":"https:\/\/doi.org\/10.1007\/s00224-021-10034-z","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"type":"print","value":"1432-4350"},{"type":"electronic","value":"1433-0490"}],"subject":[],"published":{"date-parts":[[2021,2,13]]},"assertion":[{"value":"16 January 2021","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 February 2021","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}