{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,19]],"date-time":"2025-10-19T06:03:31Z","timestamp":1760853811137},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2014,7,26]],"date-time":"2014-07-26T00:00:00Z","timestamp":1406332800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Optim Theory Appl"],"published-print":{"date-parts":[[2015,6]]},"DOI":"10.1007\/s10957-014-0603-x","type":"journal-article","created":{"date-parts":[[2014,7,25]],"date-time":"2014-07-25T16:35:15Z","timestamp":1406306115000},"page":"964-984","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Average-Case Performance of Rollout Algorithms for Knapsack Problems"],"prefix":"10.1007","volume":"165","author":[{"given":"Andrew","family":"Mastin","sequence":"first","affiliation":[]},{"given":"Patrick","family":"Jaillet","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,7,26]]},"reference":[{"key":"603_CR1","doi-asserted-by":"crossref","first-page":"245","DOI":"10.1023\/A:1009635226865","volume":"3","author":"DP Bertsekas","year":"1997","unstructured":"Bertsekas, D.P., Tsitsiklis, J., Wu, C.: Rollout algorithms for combinatorial optimization. J. Heuristics 3, 245\u2013262 (1997)","journal-title":"J. Heuristics"},{"key":"603_CR2","doi-asserted-by":"crossref","first-page":"89","DOI":"10.1023\/A:1009634810396","volume":"5","author":"DP Bertsekas","year":"1999","unstructured":"Bertsekas, D.P., Castanon, D.A.: Rollout algorithms for stochastic scheduling problems. J. Heuristics 5, 89\u2013108 (1999)","journal-title":"J. Heuristics"},{"key":"603_CR3","unstructured":"Bertsekas, D.P.: Dynamic Programming and Optimal Control, 3rd edn. Athena Scientific, Belmont, MA (2007)"},{"key":"603_CR4","doi-asserted-by":"crossref","first-page":"378","DOI":"10.1007\/s10957-011-9902-7","volume":"152","author":"L Bertazzi","year":"2012","unstructured":"Bertazzi, L.: Minimum and worst-case performance ratios of rollout algorithms. J. Optim. Theory Appl. 152, 378\u2013393 (2012)","journal-title":"J. Optim. Theory Appl."},{"key":"603_CR5","doi-asserted-by":"crossref","first-page":"113","DOI":"10.1007\/BF02331572","volume":"35","author":"K Borgwardt","year":"1991","unstructured":"Borgwardt, K., Tremel, B.: The average quality of greedy-algorithms for the subset-sum-maximization problem. Math. Methods Oper. Res. 35, 113\u2013149 (1991)","journal-title":"Math. Methods Oper. Res."},{"key":"603_CR6","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":"603_CR7","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)"},{"key":"603_CR8","first-page":"1068","volume":"9","author":"G Tesauro","year":"1997","unstructured":"Tesauro, G., Galperin, G.R.: On-line policy improvement using monte-carlo search. Adv. Neural Inf. Process. Syst. 9, 1068\u20131074 (1997)","journal-title":"Adv. Neural Inf. Process. Syst."},{"key":"603_CR9","doi-asserted-by":"crossref","first-page":"796","DOI":"10.1287\/opre.49.5.796.10608","volume":"49","author":"N Secomandi","year":"2001","unstructured":"Secomandi, N.: A rollout policy for the vehicle routing problem with stochastic demands. Oper. Res. 49, 796\u2013802 (2001)","journal-title":"Oper. Res."},{"key":"603_CR10","unstructured":"Tu, F., Pattipati, K.: Rollout strategies for sequential fault diagnosis. In: AUTOTESTCON Proceedings, pp. 269\u2013295. IEEE (2002)"},{"key":"603_CR11","doi-asserted-by":"crossref","first-page":"978","DOI":"10.1016\/j.dsp.2007.05.004","volume":"19","author":"Y Li","year":"2009","unstructured":"Li, Y., Krakow, L.W., Chong, E.K.P., Groom, K.N.: Approximate stochastic dynamic programming for sensor scheduling to track multiple targets. Digit. Signal Process. 19, 978\u2013989 (2009)","journal-title":"Digit. Signal Process."},{"key":"603_CR12","doi-asserted-by":"crossref","first-page":"198","DOI":"10.1007\/BF02612360","volume":"28","author":"S Martello","year":"1984","unstructured":"Martello, S., Toth, P.: Worst-case analysis of greedy algorithms for the subset-sum problem. Math. Program. 28, 198\u2013205 (1984)","journal-title":"Math. Program."},{"key":"603_CR13","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0166-218X(82)90055-5","volume":"4","author":"G D\u2019Atri","year":"1982","unstructured":"D\u2019Atri, G., Puech, C.: Probabilistic analysis of the subset-sum problem. Discret. Appl. Math. 4, 329\u2013334 (1982)","journal-title":"Discret. Appl. Math."},{"key":"603_CR14","first-page":"53","volume":"7","author":"U Pferschy","year":"1999","unstructured":"Pferschy, U.: Stochastic analysis of greedy algorithms for the subset sum problem. Cent. Eur. J. Oper. Res. 7, 53\u201370 (1999)","journal-title":"Cent. Eur. J. Oper. Res."},{"key":"603_CR15","first-page":"147","volume":"12","author":"K Szkatula","year":"1983","unstructured":"Szkatula, K., Libura, M.: Probabilistic analysis of simple algorithms for binary knapsack problem. Control Cybern. 12, 147\u2013157 (1983)","journal-title":"Control Cybern."},{"key":"603_CR16","unstructured":"Szkatula, K., Libura, M.: On probabilistic properties of greedy-like algorithms for the binary knapsack problem. In: Proceedings of Advanced School on Stochastics in Combinatorial Optimization pp. 233\u2013254 (1987)"},{"key":"603_CR17","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/s001860200270","volume":"57","author":"G Diubin","year":"2003","unstructured":"Diubin, G., Korbut, A.: The average behaviour of greedy algorithms for the knapsack problem: general distributions. Math. Methods Oper. Res. 57, 449\u2013479 (2003)","journal-title":"Math. Methods Oper. Res."},{"key":"603_CR18","doi-asserted-by":"crossref","first-page":"202","DOI":"10.1016\/S0167-6377(02)00222-5","volume":"31","author":"JM Calvin","year":"2003","unstructured":"Calvin, J.M., Leung, J.Y.T.: Average-case analysis of a greedy algorithm for the 0\/1 knapsack problem. Oper. Res. Lett. 31, 202\u2013210 (2003)","journal-title":"Oper. Res. Lett."},{"key":"603_CR19","doi-asserted-by":"crossref","unstructured":"Dean, B.C., Goemans, M.X., Vondrdk, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 208\u2013217. IEEE (2004)","DOI":"10.1109\/FOCS.2004.15"},{"key":"603_CR20","unstructured":"Lueker, G.S.: Average-case analysis of off-line and on-line knapsack problems. In: Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 179\u2013188. Society for Industrial and Applied Mathematics (1995)"},{"key":"603_CR21","doi-asserted-by":"crossref","unstructured":"Beier, R., V\u00f6cking, B.: Random knapsack in expected polynomial time. In: Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing, pp. 232\u2013241. ACM (2003)","DOI":"10.1145\/780542.780578"}],"container-title":["Journal of Optimization Theory and Applications"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-014-0603-x.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s10957-014-0603-x\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s10957-014-0603-x","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,6,2]],"date-time":"2019-06-02T09:58:38Z","timestamp":1559469518000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s10957-014-0603-x"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,26]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,6]]}},"alternative-id":["603"],"URL":"https:\/\/doi.org\/10.1007\/s10957-014-0603-x","relation":{},"ISSN":["0022-3239","1573-2878"],"issn-type":[{"value":"0022-3239","type":"print"},{"value":"1573-2878","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,26]]}}}