{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,6]],"date-time":"2026-03-06T23:14:32Z","timestamp":1772838872015,"version":"3.50.1"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2013,5,11]],"date-time":"2013-05-11T00:00:00Z","timestamp":1368230400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2014,5]]},"DOI":"10.1007\/s10957-013-0319-3","type":"journal-article","created":{"date-parts":[[2013,5,10]],"date-time":"2013-05-10T16:00:27Z","timestamp":1368201627000},"page":"533-552","source":"Crossref","is-referenced-by-count":11,"title":["Complexity Results and Exact Algorithms for Robust Knapsack Problems"],"prefix":"10.1007","volume":"161","author":[{"given":"Fabrice","family":"Talla\u00a0Nobibon","sequence":"first","affiliation":[]},{"given":"Roel","family":"Leus","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2013,5,11]]},"reference":[{"key":"319_CR1","doi-asserted-by":"crossref","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":"319_CR2","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 York (1990)"},{"issue":"6","key":"319_CR3","doi-asserted-by":"crossref","first-page":"489","DOI":"10.1016\/0305-0483(87)90006-5","volume":"15","author":"S. Eilon","year":"1987","unstructured":"Eilon, S.: Application of the knapsack model for budgeting. Omega Int. J. Manag. Sci. 15(6), 489\u2013494 (1987)","journal-title":"Omega Int. J. Manag. Sci."},{"key":"319_CR4","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4757-2620-6","volume-title":"Robust Discrete Optimization and its Applications","author":"P. Kouvelis","year":"1997","unstructured":"Kouvelis, P., Yu, G.: Robust Discrete Optimization and its Applications. Kluwer Academic, Norwell (1997)"},{"key":"319_CR5","doi-asserted-by":"crossref","first-page":"411","DOI":"10.1007\/PL00011380","volume":"88","author":"A. Ben-Tal","year":"2000","unstructured":"Ben-Tal, A., Nemirovski, A.: Robust solutions of linear programming problems contaminated with uncertain data. Math. Program., Ser. A 88, 411\u2013424 (2000)","journal-title":"Math. Program., Ser. A"},{"key":"319_CR6","first-page":"94","volume":"3","author":"H. Lida","year":"1999","unstructured":"Lida, H.: A note on the max\u2013min 0-1 knapsack problem. J. Comb. Optim. 3, 94\u201399 (1999)","journal-title":"J. Comb. Optim."},{"key":"319_CR7","doi-asserted-by":"crossref","first-page":"17","DOI":"10.1287\/opre.46.1.17","volume":"46","author":"A. Kleywegt","year":"1998","unstructured":"Kleywegt, A., Papastavrou, J.: The dynamic and stochastic knapsack problem. Oper. Res. 46, 17\u201335 (1998)","journal-title":"Oper. Res."},{"key":"319_CR8","doi-asserted-by":"crossref","first-page":"945","DOI":"10.1287\/opre.1080.0555","volume":"56","author":"G. Lin","year":"2008","unstructured":"Lin, G., Lu, Y., Yao, D.: The stochastic knapsack revisited: switch-over policies and dynamic pricing. Oper. Res. 56, 945\u2013957 (2008)","journal-title":"Oper. Res."},{"key":"319_CR9","doi-asserted-by":"crossref","first-page":"263","DOI":"10.1007\/PL00011424","volume":"90","author":"I. Averbakh","year":"2001","unstructured":"Averbakh, I.: On the complexity of a class of combinatorial optimization problems with uncertainty. Math. Program., Ser. A 90, 263\u2013272 (2001)","journal-title":"Math. Program., Ser. A"},{"key":"319_CR10","doi-asserted-by":"crossref","first-page":"49","DOI":"10.1007\/s10107-003-0396-4","volume":"98","author":"D. Bertsimas","year":"2003","unstructured":"Bertsimas, D., Sim, M.: Robust discrete optimization and network flows. Math. Program., Ser. B 98, 49\u201371 (2003)","journal-title":"Math. Program., Ser. B"},{"key":"319_CR11","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1287\/opre.1030.0065","volume":"52","author":"D. Bertsimas","year":"2004","unstructured":"Bertsimas, D., Sim, M.: The price of robustness. Oper. Res. 52, 35\u201353 (2004)","journal-title":"Oper. Res."},{"key":"319_CR12","doi-asserted-by":"crossref","first-page":"339","DOI":"10.1016\/j.ejor.2009.05.033","volume":"202","author":"A. Sbihi","year":"2010","unstructured":"Sbihi, A.: A cooperative local search-based algorithm for the multiple-scenario max\u2013min knapsack problem. Eur. J. Oper. Res. 202, 339\u2013346 (2010)","journal-title":"Eur. J. Oper. Res."},{"key":"319_CR13","doi-asserted-by":"crossref","first-page":"2034","DOI":"10.1016\/j.cor.2006.10.002","volume":"35","author":"F. Taniguchi","year":"2008","unstructured":"Taniguchi, F., Yamada, T., Kataoka, S.: Heuristic and exact algorithms for the max\u2013min optimization of the multi-scenario knapsack problem. Comput. Oper. Res. 35, 2034\u20132048 (2008)","journal-title":"Comput. Oper. Res."},{"key":"319_CR14","doi-asserted-by":"crossref","first-page":"628","DOI":"10.1016\/j.orl.2008.03.006","volume":"36","author":"O. Klopfenstein","year":"2008","unstructured":"Klopfenstein, O., Nace, D.: A robust approach to the chance-constrained knapsack problem. Oper. Res. Lett. 36, 628\u2013632 (2008)","journal-title":"Oper. Res. Lett."},{"key":"319_CR15","doi-asserted-by":"crossref","first-page":"297","DOI":"10.1007\/s10957-007-9334-6","volume":"137","author":"T. Assavapokee","year":"2008","unstructured":"Assavapokee, T., Realff, M., Ammons, J.: A new min\u2013max regret robust optimization approach for interval data uncertainty. J. Optim. Theory Appl. 137, 297\u2013316 (2008)","journal-title":"J. Optim. Theory Appl."},{"key":"319_CR16","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1016\/j.ejor.2008.09.012","volume":"197","author":"H. Aissi","year":"2009","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Min\u2013max and min\u2013max regret versions of combinatorial optimization problems: a survey. Eur. J. Oper. Res. 197, 427\u2013438 (2009)","journal-title":"Eur. J. Oper. Res."},{"key":"319_CR17","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.orl.2004.11.003","volume":"33","author":"E. Conde","year":"2005","unstructured":"Conde, E.: On the complexity of the continuous unbounded knapsack problem with uncertain coefficients. Oper. Res. Lett. 33, 481\u2013485 (2005)","journal-title":"Oper. Res. Lett."},{"key":"319_CR18","doi-asserted-by":"crossref","first-page":"281","DOI":"10.1016\/j.ejor.2006.03.023","volume":"179","author":"H. Aissi","year":"2007","unstructured":"Aissi, H., Bazgan, C., Vanderpooten, D.: Approximation of min\u2013max and min\u2013max regret versions of some combinatorial optimization problems. Eur. J. Oper. Res. 179, 281\u2013290 (2007)","journal-title":"Eur. J. Oper. Res."},{"key":"319_CR19","doi-asserted-by":"crossref","unstructured":"Talla Nobibon, F., Leus, R.: Complexity results and exact algorithms for robust knapsack problems. Research report KBI 1118, Faculty of Business and Economics, KU, Leuven (2011)","DOI":"10.2139\/ssrn.1967411"},{"key":"319_CR20","doi-asserted-by":"crossref","first-page":"414","DOI":"10.1287\/mnsc.45.3.414","volume":"45","author":"S. Martello","year":"1999","unstructured":"Martello, S., Pisinger, D., Toth, P.: Dynamic programming and strong bounds for the 0\u20131 knapsack problem. Manag. Sci. 45, 414\u2013424 (1999)","journal-title":"Manag. Sci."},{"key":"319_CR21","doi-asserted-by":"crossref","first-page":"2271","DOI":"10.1016\/j.cor.2004.03.002","volume":"32","author":"D. Pisinger","year":"2005","unstructured":"Pisinger, D.: Where are the hard knapsack problems? Comput. Oper. Res. 32, 2271\u20132284 (2005)","journal-title":"Comput. Oper. Res."},{"key":"319_CR22","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1287\/opre.44.2.407","volume":"44","author":"G. Yu","year":"1996","unstructured":"Yu, G.: On the max\u2013min 0\u20131 knapsack problem with robust optimization applications. Oper. Res. 44, 407\u2013415 (1996)","journal-title":"Oper. Res."},{"key":"319_CR23","doi-asserted-by":"crossref","first-page":"656","DOI":"10.1002\/nav.20237","volume":"54","author":"M. Kress","year":"2007","unstructured":"Kress, M., Penn, M., Polukarov, M.: The minmax multidimensional knapsack problem with application to a chance-constrained problem. Nav. Res. Logist. 54, 656\u2013666 (2007)","journal-title":"Nav. Res. Logist."},{"key":"319_CR24","doi-asserted-by":"crossref","first-page":"103","DOI":"10.1111\/j.1475-3995.2010.00786.x","volume":"18","author":"R. Kalai","year":"2011","unstructured":"Kalai, R., Vanderpooten, D.: Lexicographic \u03b1-robust knapsack problem: complexity results. Int. Trans. Oper. Res. 18, 103\u2013113 (2011)","journal-title":"Int. Trans. Oper. Res."},{"key":"319_CR25","first-page":"107","volume":"6","author":"G. Chen","year":"2003","unstructured":"Chen, G., Hwang, H., Tsai, T.: Efficient maxima-finding algorithms for random planar samples. Discrete Math. Theor. Comput. Sci. 6, 107\u2013122 (2003)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"319_CR26","doi-asserted-by":"crossref","first-page":"2093","DOI":"10.1016\/j.cor.2006.10.013","volume":"35","author":"T. Assavapokee","year":"2008","unstructured":"Assavapokee, T., Realff, M., Ammons, J., Hong, I.: Scenario relaxation algorithm for finite scenario-based min\u2013max regret and min\u2013max relative regret robust optimization. Comput. Oper. Res. 35, 2093\u20132102 (2008)","journal-title":"Comput. Oper. Res."},{"key":"319_CR27","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1016\/j.disopt.2005.07.001","volume":"2","author":"I. Averbakh","year":"2005","unstructured":"Averbakh, I.: Computing and minimizing the relative regret in combinatorial optimization with interval data. Discrete Optim. 2, 273\u2013287 (2005)","journal-title":"Discrete Optim."}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-013-0319-3.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10957-013-0319-3\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-013-0319-3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,7,13]],"date-time":"2019-07-13T17:16:58Z","timestamp":1563038218000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10957-013-0319-3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,11]]},"references-count":27,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2014,5]]}},"alternative-id":["319"],"URL":"https:\/\/doi.org\/10.1007\/s10957-013-0319-3","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,11]]}}}