{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,28]],"date-time":"2026-09-28T02:48:15Z","timestamp":1790563695331,"version":"4.1.0"},"reference-count":33,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"4","funder":[{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["399\/17"],"award-info":[{"award-number":["399\/17"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100003977","name":"Israel Science Foundation","doi-asserted-by":"publisher","award":["1074\/21"],"award-info":[{"award-number":["1074\/21"]}],"id":[{"id":"10.13039\/501100003977","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100006221","name":"United States - Israel Binational Science Foundation","doi-asserted-by":"publisher","award":["2018095"],"award-info":[{"award-number":["2018095"]}],"id":[{"id":"10.13039\/100006221","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2021,1]]},"abstract":"<jats:p>In this paper we go one step further in the automatic generation of FPTASes for multistage stochastic dynamic programs with scalar state and action spaces, in which the cost-to-go functions have a monotone structure in the state variable. While there exist a few frameworks for automatic generation of FPTASes, so far none of them is general and simple enough to be extensively used. We believe that our framework has these two attributes and has great potential to attract interest from both the operations research and theoretical computer science communities. Moreover, it seems very reasonable that many intractable problems that currently do not admit an FPTAS, can be formulated as DPs that fit into our framework and therefore will admit a first FPTAS. Our results are achieved by a combination of Bellman equation formulations, the technique of $K$-approximation sets and functions, and in particular the calculus of $K$-approximation functions.<\/jats:p>","DOI":"10.1137\/19m1308633","type":"journal-article","created":{"date-parts":[[2021,11,8]],"date-time":"2021-11-08T12:18:05Z","timestamp":1636373885000},"page":"2679-2722","source":"Crossref","is-referenced-by-count":8,"title":["Automatic Generation of FPTASes for Stochastic Monotone Dynamic Programs Made Easier"],"prefix":"10.1137","volume":"35","author":[{"given":"Tzvi","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6098-9792","authenticated-orcid":true,"given":"Nir","family":"Halman","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2021,11,8]]},"reference":[{"key":"atypb1","unstructured":"T. Alon,\n                      Fully Polynomial Time Approximation Schemes (FPTAS) for Some Counting Problems\n                      , Master thesis in the Department of Statistics, the Hebrew University of Jerusalem, Israel; also available online, preprint, arXiv:1611.00992, 2016."},{"key":"atypb2","unstructured":"D. Bertsekas,\n                      Dynamic Programming and Optimal Control\n                      , Volume 1, Athena Scientific, Belmont, MA, 1995."},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1007\/s11590-018-1251-0"},{"key":"atypb4","unstructured":"M.R. Garey and D.S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W.H. Freeman, New York, 1979."},{"key":"atypb5","unstructured":"P. Gawrychowski, L. Markin, and O. Weimann,\n                      A Faster FPTAS for \\#Knapsack\n                      , in Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018), LIPIcs. Leibniz Int. Proc. Inform. 107, Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018, pp. 64:1-64:13."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2016.06.015"},{"key":"atypb7","first-page":"1157","volume":"32","author":"Halman N.","year":"2020","journal-title":"INFORMS J. Comput."},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1007\/s10951-019-00616-8"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1137\/130925153"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1287\/moor.1090.0391"},{"key":"atypb11","doi-asserted-by":"publisher","DOI":"10.1007\/s00291-018-0543-1"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2018.04.013"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2009.03.002"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1137\/18M1208423"},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2017.11.001"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1110.1031"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1145\/321906.321909"},{"key":"atypb18","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009626427432"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1504\/IJPS.2012.050127"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"H. Kellerer, U. Pferschy, and D. Pisinger,\n                      Knapsack Problems\n                      , Vol. 1. Springer, Berlin, 2004.","DOI":"10.1007\/978-3-540-24777-7_1"},{"key":"atypb21","first-page":"415","author":"Korte B.","year":"1981","journal-title":"New York"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1520-6750(199808)45:5<511::AID-NAV5>3.0.CO;2-6"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1287\/opre.1120.1093"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.03.006"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2019.04.001"},{"key":"atypb26","doi-asserted-by":"publisher","DOI":"10.1145\/321921.321934"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1287\/opre.43.1.187"},{"key":"atypb28","doi-asserted-by":"crossref","unstructured":"D. Simchi-Levi, X. Chen, and J. Bramel,\n                      The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management\n                      , 3rd ed., Springer, Berlin, 2014.","DOI":"10.1007\/978-1-4614-9149-1"},{"key":"atypb29","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800030106"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1137\/100789269"},{"key":"atypb31","doi-asserted-by":"publisher","DOI":"10.1137\/11083976X"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/0211023"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1287\/ijoc.12.1.57.11901"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/19M1308633","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:06:45Z","timestamp":1787317605000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/19M1308633"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,1]]},"references-count":33,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,1]]}},"alternative-id":["10.1137\/19M1308633"],"URL":"https:\/\/doi.org\/10.1137\/19m1308633","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,1]]}}}