{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,10]],"date-time":"2026-02-10T05:24:03Z","timestamp":1770701043444,"version":"3.49.0"},"publisher-location":"Berlin, Heidelberg","reference-count":18,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783642366932","type":"print"},{"value":"9783642366949","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2013]]},"DOI":"10.1007\/978-3-642-36694-9_9","type":"book-chapter","created":{"date-parts":[[2013,3,11]],"date-time":"2013-03-11T10:08:39Z","timestamp":1362996519000},"page":"98-109","source":"Crossref","is-referenced-by-count":17,"title":["A Complexity and Approximability Study of the Bilevel Knapsack Problem"],"prefix":"10.1007","author":[{"given":"Alberto","family":"Caprara","sequence":"first","affiliation":[]},{"given":"Margarida","family":"Carvalho","sequence":"additional","affiliation":[]},{"given":"Andrea","family":"Lodi","sequence":"additional","affiliation":[]},{"given":"Gerhard J.","family":"Woeginger","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"9_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. Operations Research Letters\u00a037, 215\u2013218 (2009)","journal-title":"Operations Research Letters"},{"key":"9_CR2","unstructured":"Brotcorne, L., Hanafi, S., Mansi, R.: One-level reformulation of the bilevel knapsack problem using dynamic programming. Technical Report, Universit\u00e9 de Valenciennes et du Hainaut-Cambr\u00e9sis, France (2011)"},{"key":"9_CR3","volume-title":"Foundations of Bilevel Programming","author":"S. Dempe","year":"2002","unstructured":"Dempe, S.: Foundations of Bilevel Programming. Kluwer Academic Publishers, Dordrecht (2002)"},{"key":"9_CR4","first-page":"93","volume":"8","author":"S. Dempe","year":"2000","unstructured":"Dempe, S., Richter, K.: Bilevel programming with Knapsack constraint. Central European Journal of Operations Research\u00a08, 93\u2013107 (2000)","journal-title":"Central European Journal of Operations Research"},{"key":"9_CR5","unstructured":"DeNegre, S.: Interdiction and discrete bilevel linear programming. Ph.D. dissertation, Lehigh University (2011)"},{"key":"9_CR6","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-1-4613-0307-7_6","volume-title":"Multilevel Optimization: Algorithms and Applications","author":"X. Deng","year":"1998","unstructured":"Deng, X.: Complexity issues in bilevel linear programming. In: Migdalas, A., Pardalos, P.M., V\u00e4rbrand, P. (eds.) Multilevel Optimization: Algorithms and Applications, pp. 149\u2013164. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"9_CR7","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/978-1-4613-0307-7_7","volume-title":"Multilevel Optimization: Algorithms and Applications","author":"T. Dud\u00e1s","year":"1998","unstructured":"Dud\u00e1s, T., Klinz, B., Woeginger, G.J.: The computational complexity of multi-level bottleneck programming problems. In: Migdalas, A., Pardalos, P.M., V\u00e4rbrand, P. (eds.) Multilevel Optimization: Algorithms and Applications, pp. 165\u2013179. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"9_CR8","unstructured":"Eggermont, C., Woeginger, G.J.: Motion planning with pulley, rope, and baskets. In: Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012. Leibniz International Proceedings in Informatics, vol.\u00a014, pp. 374\u2013383 (2012)"},{"key":"9_CR9","doi-asserted-by":"publisher","first-page":"212","DOI":"10.1112\/jlms\/s1-16.4.212","volume":"16","author":"P. Erd\u0151s","year":"1941","unstructured":"Erd\u0151s, P., Tur\u00e1n, P.: On a problem of Sidon in additive number theory, and on some related problems. Journal of the London Mathematical Society\u00a016, 212\u2013215 (1941)","journal-title":"Journal of the London Mathematical Society"},{"key":"9_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"M.R. 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":"9_CR11","doi-asserted-by":"publisher","first-page":"146","DOI":"10.1007\/BF01586088","volume":"32","author":"R. Jeroslow","year":"1985","unstructured":"Jeroslow, R.: The polynomial hierarchy and a simple model for competitive analysis. Mathematical Programming\u00a032, 146\u2013164 (1985)","journal-title":"Mathematical Programming"},{"key":"9_CR12","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1007\/978-1-4613-3557-3_15","volume-title":"Minimax and Applications","author":"K. Ko","year":"1995","unstructured":"Ko, K., Lin, C.-L.: On the complexity of min-max optimization problems and their approximation. In: Du, D.-Z., Pardalos, P.M. (eds.) Minimax and Applications, pp. 219\u2013239. Kluwer Academic Publishers, Dordrecht (1995)"},{"key":"9_CR13","doi-asserted-by":"publisher","first-page":"339","DOI":"10.1287\/moor.4.4.339","volume":"4","author":"E.L. Lawler","year":"1979","unstructured":"Lawler, E.L.: Fast approximation algorithms for knapsack problems. Mathematics of Operations Research\u00a04, 339\u2013356 (1979)","journal-title":"Mathematics of Operations Research"},{"key":"9_CR14","doi-asserted-by":"crossref","unstructured":"Mansi, R., Alves, C., de Carvalho, J.M.V., Hanafi, S.: An exact algorithm for bilevel 0-1 knapsack problems. Mathematical Problems in Engineering, Article ID 504713 (2012)","DOI":"10.1155\/2012\/504713"},{"key":"9_CR15","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0307-7","volume-title":"Multilevel Optimization: Algorithms and Applications","author":"A. Migdalas","year":"1998","unstructured":"Migdalas, A., Pardalos, P.M., V\u00e4rbrand, P.: Multilevel Optimization: Algorithms and Applications. Kluwer Academic Publishers, Dordrecht (1998)"},{"key":"9_CR16","unstructured":"Papadimitriou, C.H.: Computational Complexity. Addison-Wesley (1994)"},{"key":"9_CR17","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1016\/j.tcs.2007.03.006","volume":"382","author":"K. Pruhs","year":"2007","unstructured":"Pruhs, K., Woeginger, G.J.: Approximation schemes for a class of subset selection problems. Theoretical Computer Science\u00a0382, 151\u2013156 (2007)","journal-title":"Theoretical Computer Science"},{"key":"9_CR18","unstructured":"Umans, C.: Hardness of approximating \n                  \n                    \n                  \n                  ${\\sum^{\\rm p}_{2}}$\n                 minimization problems. In: Proceedings of the 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, pp. 465\u2013474 (1999)"}],"container-title":["Lecture Notes in Computer Science","Integer Programming and Combinatorial Optimization"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-642-36694-9_9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,11]],"date-time":"2019-05-11T17:40:27Z","timestamp":1557596427000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-642-36694-9_9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013]]},"ISBN":["9783642366932","9783642366949"],"references-count":18,"URL":"https:\/\/doi.org\/10.1007\/978-3-642-36694-9_9","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013]]}}}