Fully Polynomial Time Approximation Schemes for Robust Multistage Decision Making

References

• Agra A, Santos M, Nace D, Poss M (2016) A dynamic programming approach for a class of robust optimization problems. SIAM J. Optim. 26(3):1799–1823.Crossref, Google Scholar
• Alon T, Halman N (2021) Automatic generation of FPTASes for stochastic monotone dynamic programs made easier. SIAM J. Discrete Math. 35(4):2679–2722.Crossref, Google Scholar
• Ben-Tal A, Ghaoui LE, Nemirovski A (2009) Robust Optimization. Princeton Series in Applied Mathematics (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• Ben-Tal A, Housni OE, Goyal V (2020) A tractable approach for designing piecewise affine policies in two-stage adjustable robust optimization. Math. Programming 182(1):57–102.Crossref, Google Scholar
• Ben-Tal A, Goryashko A, Guslitzer E, Nemirovski A (2004) Adjustable robust solutions of uncertain linear programs. Math. Programming 99(2):351–376.Crossref, Google Scholar
• Bertsimas D, Sim M (2004) The price of robustness. Oper. Res. 52(1):35–53.Link, Google Scholar
• Bertsimas D, Thiele A (2006) A robust optimization approach to inventory theory. Oper. Res. 54(1):150–168.Link, Google Scholar
• Bienstock D, Özbay N (2008) Computing robust basestock levels. Discrete Optim. 5(2):389–414.Crossref, Google Scholar
• Bougeret M, Pessoa A, Poss M (2019) Robust scheduling with budgeted uncertainty. Discrete Appl. Math. 261:93–107.Crossref, Google Scholar
• Chubanov S, Kovalyov M, Pesch E (2006) An FPTAS for a single-item capacitated economic lot-sizing problem with monotone cost structure. Math. Programming 106:453–466.Crossref, Google Scholar
• Dean B, Goemans M, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Feige U, Jain K, Mahdian M, Mirrokni V (2007) Robust combinatorial optimization with exponential scenarios. Internat. Conf. Integer Programming Combin. Optim. 12th Internat. IPCO Conf. (Springer, Berlin, Heidelberg), 439–453.Google Scholar
• Florian M, Lenstra J, Rinnooy Kan A (1980) Deterministic production planning: Algorithms and complexity. Management Sci. 26(7):669–679.Link, Google Scholar
• Gopalan P, Klivans A, Meka R, Štefankovič D, Vempala S, Vigoda E (2011) An FPTAS for #Knapsack and related counting problems. IEEE 52nd Annual Sympos. Foundations Comput. Sci. (FOCS) (IEEE, Piscataway, NJ), 817–826.Google Scholar
• Guillaume R, Kasperski A, Zieliński P (2020) Production planning under demand uncertainty: A budgeted uncertainty approach. Neufeld JS, Buscher U, Lasch R, Möst D, Schönberger J, eds. Oper. Res. Proc. 2019 (Springer, Cham, Switzerland), 431–437.Google Scholar
• Halman N (2016) A deterministic fully polynomial time approximation scheme for counting integer knapsack solutions made easy. Theoret. Comput. Sci. 645:41–47.Crossref, Google Scholar
• Halman N (2020) Provably near-optimal approximation schemes for implicit stochastic and for sample-based dynamic programs. INFORMS J. Comput. 32(4):1157–1181.Abstract, Google Scholar
• Halman N, Nannicini G (2019) Toward breaking the curse of dimensionality: An FPTAS for stochastic dynamic programs with multidimensional action and scalar state. SIAM J. Optim. 29(2):1131–1163.Crossref, Google Scholar
• Halman N, Nannicini G (2022) Fully polynomial time (σ,π)-approximation schemes for continuous nonlinear newsvendor and continuous stochastic dynamic programs. Math. Programming 195(1–2):183–242.Crossref, Google Scholar
• Halman N, Nannicini G, Orlin J (2015) A computationally efficient FPTAS for convex stochastic dynamic programs. SIAM J. Optim. 25(1):317–350.Crossref, Google Scholar
• Halman N, Orlin JB, Simchi-Levi D (2012) Approximating the nonlinear newsvendor and single-item stochastic lot-sizing problems when data are given by an oracle. Oper. Res. 60(2):429–446.Link, Google Scholar
• Halman N, Klabjan D, Li CL, Orlin J, Simchi-Levi D (2014) Fully polynomial time approximation schemes for stochastic dynamic programs. SIAM J. Discrete Math. 28(4):1725–1796.Crossref, Google Scholar
• Halman N, Klabjan D, Mostagir M, Orlin J, Simchi-Levi D (2009) A fully polynomial time approximation scheme for single-item stochastic inventory control with discrete demand. Math. Oper. Res. 34(3):674–685.Link, Google Scholar
• Hochbaum D (1995) A nonlinear Knapsack problem. Oper. Res. Lett. 17(3):103–110.Crossref, Google Scholar
• Housni OE, Goyal V (2021) On the optimality of affine policies for budgeted uncertainty sets. Math. Oper. Res. 46(2):674–711.Link, Google Scholar
• Ibarra O, Kim C (1975) Fast approximation algorithms for the knapsack and sum of subset problems. J. ACM. 22(4):463–468.Crossref, Google Scholar
• Kasperski A, Zieliński P (2007) On the existence of an FPTAS for minmax regret combinatorial optimization problems with interval data. Oper. Res. Lett. 35(4):525–532.Crossref, Google Scholar
• Kellerer H, Pferschy U (2004) Improved dynamic programming in connection with an FPTAS for the knapsack problem. J. Combin. Optim. 8(1):5–11.Crossref, Google Scholar
• Lawler E (1979) Fast approximation algorithms for knapsack problems. Math. Oper. Res. 4(4):339–356.Link, Google Scholar
• Murota K (2003) Discrete Convex Analysis (SIAM, Philadelphia).Crossref, Google Scholar
• Ng CT, Kovalyov MY, Cheng TCE (2010) A simple FPTAS for a single-item capacitated economic lot-sizing problem with a monotone cost structure. Eur. J. Oper. Res. 200(2):621–624.Crossref, Google Scholar
• Papadaki K, Powell W (2003) An adaptive dynamic programming algorithm for stochastic multiproduct batch dispatch problem. Naval Res. Logist. 50(7):742–769.Crossref, Google Scholar
• Rizzi R, Tomescu A (2019) Faster FPTASes for counting and random generation of Knapsack solutions. Inform. Comput. 267:135–144.Google Scholar
• Shapiro A (2012) Minimax and risk averse multistage stochastic programming. Eur. J. Oper. Res. 219(3):719–726.Crossref, Google Scholar
• Simchi-Levi D, Chen X, Bramel J (2014) The Logic of Logistics: Theory, Algorithms, and Applications for Logistics Management, 3rd ed. (Springer-Verlag, New York).Crossref, Google Scholar
• Štefankovič D, Vempala S, Vigoda E (2012) A deterministic polynomial-time approximation scheme for counting knapsack solutions. SIAM J. Comput. 41(2):356–366.Crossref, Google Scholar
• Van Hoesel C, Wagelmans A (2001) Fully polynomial approximation schemes for single-item capacitated economic lot-sizing problems. Math. Oper. Res. 26(2):339–357.Link, Google Scholar