{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,26]],"date-time":"2025-03-26T17:59:27Z","timestamp":1743011967522,"version":"3.40.3"},"publisher-location":"Cham","reference-count":20,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030181253"},{"type":"electronic","value":"9783030181260"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-18126-0_11","type":"book-chapter","created":{"date-parts":[[2019,4,14]],"date-time":"2019-04-14T23:02:19Z","timestamp":1555282939000},"page":"121-132","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["An FPTAS for Stochastic Unbounded Min-Knapsack Problem"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9682-2476","authenticated-orcid":false,"given":"Zhihao","family":"Jiang","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6775-1421","authenticated-orcid":false,"given":"Haoyu","family":"Zhao","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,4,9]]},"reference":[{"issue":"4","key":"11_CR1","doi-asserted-by":"publisher","first-page":"557","DOI":"10.1287\/moor.7.4.557","volume":"7","author":"D Assaf","year":"1982","unstructured":"Assaf, D.: Renewal decisions when category life distributions are of phase-type. Math. Oper. Res. 7(4), 557\u2013567 (1982)","journal-title":"Math. Oper. Res."},{"key":"11_CR2","doi-asserted-by":"crossref","unstructured":"Bhalgat, A., Goel, A., Khanna, S.: Improved approximation results for stochastic knapsack problems. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, Philadelphia (2011)","DOI":"10.1137\/1.9781611973082.127"},{"key":"11_CR3","doi-asserted-by":"crossref","unstructured":"Bhalgat, A.: A (2 + $$\\epsilon $$)-approximation algorithm for the stochastic knapsack problem. Manuscript (2012)","DOI":"10.1137\/1.9781611973082.127"},{"key":"11_CR4","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1007\/978-3-540-68891-4_20","volume-title":"Integer Programming and Combinatorial Optimization","author":"T Carnes","year":"2008","unstructured":"Carnes, T., Shmoys, D.: Primal-dual schema for capacitated covering problems. In: Lodi, A., Panconesi, A., Rinaldi, G. (eds.) IPCO 2008. LNCS, vol. 5035, pp. 288\u2013302. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-68891-4_20"},{"issue":"1\u20132","key":"11_CR5","first-page":"15","volume":"10","author":"J Csirik","year":"1991","unstructured":"Csirik, J., Frenk, J.B.G., Labbe, M., Zhang, S.: Heuristics for the 0-1 min-knapsack problem. Acta Cybern. 10(1\u20132), 15\u201320 (1991)","journal-title":"Acta Cybern."},{"key":"11_CR6","unstructured":"Dean, B.C., Goemans, M.X., Vondrak, J.: Approximating the stochastic knapsack problem: the benefit of adaptivity. In: Annual IEEE Symposium on Foundations of Computer Science, pp. 208\u2013217. IEEE Computer Society, Los Alamitos (2004)"},{"issue":"5","key":"11_CR7","doi-asserted-by":"publisher","first-page":"554","DOI":"10.1287\/mnsc.24.5.554","volume":"24","author":"C Derman","year":"1978","unstructured":"Derman, C., Lieberman, G.J., Ross, S.M.: A renewal decision problem. Manag. Sci. 24(5), 554\u2013561 (1978)","journal-title":"Manag. Sci."},{"issue":"3","key":"11_CR8","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1145\/2876506","volume":"12","author":"A Deshpande","year":"2016","unstructured":"Deshpande, A., Hellerstein, L., Kletenik, D.: Approximation algorithms for stochastic submodular set cover with applications to boolean function evaluation and min-knapsack. ACM Trans. Algorithms 12(3), 28 (2016)","journal-title":"ACM Trans. Algorithms"},{"key":"11_CR9","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W. H. Freeman, New York (2002)"},{"issue":"2","key":"11_CR10","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1016\/S0167-6377(99)00066-8","volume":"26","author":"MM Guntzer","year":"2000","unstructured":"Guntzer, M.M., Jungnickel, D.: Approximate minimization algorithms for the 0\/1 knapsack and subset-sum problem. Oper. Res. Lett. 26(2), 55\u201366 (2000)","journal-title":"Oper. Res. Lett."},{"key":"11_CR11","doi-asserted-by":"crossref","unstructured":"Gupta, A., Krishnaswamy, R., Molinaro, M., Ravi, R.: Approximation algorithms for correlated knapsacks and non-martingale bandits. In: IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, 22\u201325 October 2011, pp. 827\u2013836 (2011)","DOI":"10.1109\/FOCS.2011.48"},{"key":"11_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1007\/978-3-642-12450-1_17","volume-title":"Approximation and Online Algorithms","author":"X Han","year":"2010","unstructured":"Han, X., Makino, K.: Online minimization knapsack problem. In: Bampis, E., Jansen, K. (eds.) WAOA 2009. LNCS, vol. 5893, pp. 182\u2013193. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-12450-1_17"},{"issue":"4","key":"11_CR13","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1145\/321906.321909","volume":"22","author":"OH Ibarra","year":"1975","unstructured":"Ibarra, O.H., Kim, C.E.: Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM (JACM) 22(4), 463\u2013468 (1975)","journal-title":"J. ACM (JACM)"},{"key":"11_CR14","doi-asserted-by":"publisher","first-page":"148","DOI":"10.1016\/j.ejc.2017.07.016","volume":"68","author":"K Jansen","year":"2018","unstructured":"Jansen, K., Kraft, S.E.: A faster FPTAS for the unbounded knapsack problem. Eur. J. Comb. 68, 148\u2013174 (2018)","journal-title":"Eur. J. Comb."},{"key":"11_CR15","doi-asserted-by":"publisher","first-page":"235","DOI":"10.1007\/978-3-540-24777-7_9","volume-title":"Knapsack Problems","author":"H Kellerer","year":"2004","unstructured":"Kellerer, H., Pferschy, U., Pisinger, D.: Multidimensional knapsack problems. In: Kellerer, H., Pferschy, U., Pisinger, D. (eds.) Knapsack Problems, pp. 235\u2013283. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-24777-7_9"},{"issue":"3","key":"11_CR16","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.orl.2014.02.004","volume":"42","author":"J Li","year":"2014","unstructured":"Li, J., Shi, T.L.: A fully polynomial-time approximation scheme for approximating a sum of random variables. Oper. Res. Lett. 42(3), 197\u2013202 (2014)","journal-title":"Oper. Res. Lett."},{"key":"11_CR17","doi-asserted-by":"crossref","unstructured":"Li, J., Yuan, W.: Stochastic combinatorial optimization via poisson approximation. In: Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, STOC 2013, pp. 971\u2013980. ACM, New York (2013)","DOI":"10.1145\/2488608.2488731"},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"Ma, W.: Improvements and generalizations of stochastic knapsack and multi-armed bandit approximation algorithms. In: Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (2014)","DOI":"10.1137\/1.9781611973402.85"},{"issue":"7","key":"11_CR19","doi-asserted-by":"publisher","first-page":"740","DOI":"10.1109\/26.31166","volume":"37","author":"KW Ross","year":"1989","unstructured":"Ross, K.W., Tsang, D.H.: The stochastic knapsack problem. IEEE Trans. Commun. 37(7), 740\u2013747 (1989)","journal-title":"IEEE Trans. Commun."},{"issue":"1","key":"11_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1145\/321864.321873","volume":"22","author":"S Sahni","year":"1975","unstructured":"Sahni, S.: Approximate algorithms for 0\/1 knapsack problem. J. ACM 22(1), 115\u2013124 (1975)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Frontiers in Algorithmics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-18126-0_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,7]],"date-time":"2024-03-07T13:18:53Z","timestamp":1709817533000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-18126-0_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030181253","9783030181260"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-18126-0_11","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"9 April 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"FAW","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Frontiers in Algorithmics","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Sanya","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"faw2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/iiis.tsinghua.edu.cn\/~jianli\/FAW2019\/FAW2019.html","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}