Technical Note—Improved Sample-Complexity Bounds in Stochastic Optimization

References

• Abolhassani M, Esfandiari H, Hajiaghayi M, Mahini H, Malec D, Srinivasan A (2015) Selling tomorrow’s bargains today. Weiss G, Yolum P, eds. Proc. 2015 Internat. Conf. Autonomous Agents Multiagent Systems (International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC), 337–345.Google Scholar
• Bansal N, Gupta A, Li J, Mestre J, Nagarajan V, Rudra A (2012) When LP is the cure for your matching woes: Improved bounds for stochastic matchings. Algorithmica 63(4):733–762.Crossref, Google Scholar
• Beale EM (1955) On minimizing a convex function subject to linear inequalities. J. Roy. Statist. Soc. B 17(2):173–184.Crossref, Google Scholar
• Besbes O, Gur Y, Zeevi A (2015) Non-stationary stochastic optimization. Oper. Res. 63(5):1227–1244.Link, Google Scholar
• Birge JR, Louveaux F (2011) Introduction to Stochastic Programming, 2nd ed. (Springer-Verlag, New York).Crossref, Google Scholar
• Canetti R, Even G, Goldreich O (1995) Lower bounds for sampling algorithms for estimating the average. Inform. Processing Lett. 53(1):17–25.Crossref, Google Scholar
• Charikar M, Chekuri C, Pál M (2005) Sampling bounds for stochastic optimization. Dinur I, Jansen K, Naor J, Rolim J, eds. Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques (Springer, Berlin), 257–269.Crossref, Google Scholar
• Chen N, Immorlica N, Karlin AR, Mahdian M, Rudra A (2009) Approximating matches made in heaven. Albers S, Marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Automata, Languages and Programming (Springer, Berlin), 266–278.Crossref, Google Scholar
• Dantzig GB (1955) Linear programming under uncertainty. Management Sci. 1(3–4):197–206.Link, Google Scholar
• Dean BC, Goemans MX, Vondrák J (2008) Approximating the stochastic knapsack problem: The benefit of adaptivity. Math. Oper. Res. 33(4):945–964.Link, Google Scholar
• Dieker A, Ghosh S, Squillante MS (2016) Optimal resource capacity management for stochastic networks. Oper. Res. 65(1):221–241.Link, Google Scholar
• Elmachtoub AN, Levi R (2016) Supply chain management with online customer selection. Oper. Res. 64(2):458–473.Link, Google Scholar
• Garg N, Gupta A, Leonardi S, Sankowski P (2008) Stochastic analyses for online combinatorial optimization problems. Teng S-H, ed. Proc. Nineteenth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 942–951.Google Scholar
• Goyal V, Levi R, Segev D (2016) Near-optimal algorithms for the assortment planning problem under dynamic substitution and stochastic demand. Oper. Res. 64(1):219–235.Link, Google Scholar
• Gupta A, Kumar A (2009) A constant-factor approximation for stochastic Steiner forest. Mitzenmacher M, ed. Proc. Forty-First Annual ACM Sympos. Theory Comput. (ACM, New York), 659–668.Google Scholar
• Gupta A, Ravi R, Sinha A (2007) LP rounding approximation algorithms for stochastic network design. Math. Oper. Res. 32(2):345–364.Link, Google Scholar
• Gupta A, Pál M, Ravi R, Sinha A (2004) Boosted sampling: Approximation algorithms for stochastic optimization. Babai L, ed. Proc. Thirty-Sixth Annual ACM Sympos. Theory Comput. (ACM, New York), 417–426.Google Scholar
• Immorlica N, Karger D, Minkoff M, Mirrokni VS (2004) On the costs and benefits of procrastination: Approximation algorithms for stochastic combinatorial optimization problems. Munro I, ed. Proc. Fifteenth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 691–700.Google Scholar
• Jaillet P, Qi J, Sim M (2016) Routing optimization under uncertainty. Oper. Res. 64(1):186–200.Link, Google Scholar
• Kleywegt AJ, Shapiro A, Homem-de Mello T (2002) The sample average approximation method for stochastic discrete optimization. SIAM J. Optim. 12(2):479–502.Crossref, Google Scholar
• Levi R, Pál M, Roundy RO, Shmoys DB (2007) Approximation algorithms for stochastic inventory control models. Math. Oper. Res. 32(2):284–302.Link, Google Scholar
• Papier F (2016) Supply allocation under sequential advance demand information. Oper. Res. 64(2):341–361.Link, Google Scholar
• Pu S, Garcia A (2018) A flocking-based approach for distributed stochastic optimization. Oper. Res. 66(1):267–281.Link, Google Scholar
• Raginsky M, Nedić A (2016) Online discrete optimization in social networks in the presence of Knightian uncertainty. Oper. Res. 64(3):662–679.Link, Google Scholar
• Ravi R, Sinha A (2006) Hedging uncertainty: Approximation algorithms for stochastic optimization problems. Math. Programming 108(1):97–114.Crossref, Google Scholar
• Russo D, Roy BV (2018) Learning to optimize via information-directed sampling. Oper. Res. 66(1):230–252.Link, Google Scholar
• Ruszczynski AP, Shapiro A (2003) Stochastic Programming, vol. 10 (Elsevier, Amsterdam).Crossref, Google Scholar
• Shapiro A (2003) Monte Carlo sampling methods. Handbook Oper. Res. Management Sci. 10:353–425.Google Scholar
• Shapiro A, Dentcheva D, Ruszczynski A (2014) Lectures on Stochastic Programming—Modeling and Theory, vol. 16, 2nd ed. (SIAM, Philadelphia).Crossref, Google Scholar
• Shmoys DB, Swamy C (2004) The sample average approximation method for 2-stage stochastic optimization. Accessed September 30, 2023, https://www.math.uwaterloo.ca/~cswamy/papers/SAAproof.pdf.Google Scholar
• Shmoys DB, Swamy C (2006) An approximation scheme for stochastic linear programming and its application to stochastic integer programs. J. ACM 53(6):978–1012.Crossref, Google Scholar
• Srinivasan A (2007) Approximation algorithms for stochastic and risk-averse optimization. Gabow H, ed. Proc. Eighteenth Annual ACM-SIAM Sympos. Discrete Algorithms (Society for Industrial and Applied Mathematics, Philadelphia), 1305–1313.Google Scholar
• Tarjan R (2009) Advanced algorithm design. Lecture notes, Princeton University. Accessed September 30, 2023, https://www.cs.princeton.edu/courses/archive/fall09/cos521/Handouts/probabilityandcomputing.pdf.Google Scholar
• Wang X, Truong VA (2018) Multi-priority online scheduling with cancellations. Oper. Res. 66(1):104–122.Link, Google Scholar