Logarithmic Regret in the Dynamic and Stochastic Knapsack Problem with Equal Rewards

References

• Arlotto A, Gurvich I (2019) Uniformly bounded regret in the multi-secretary problem. Stochastic Systems 9(3):231–260.Link, Google Scholar
• Arlotto A, Nguyen VV, Steele JM (2015) Optimal online selection of a monotone subsequence: A central limit theorem. Stochastic Processes Their Appl. 125(9):3596–3622.Google Scholar
• Arlotto A, Wei Y, Xie X (2018) An adaptive O(log n)-optimal policy for the online selection of a monotone subsequence from a random sample. Random Structures Algorithms 52(1):41–53.Google Scholar
• Balseiro SR, Brown DB (2019) Approximations to stochastic dynamic programs via information relaxation duality. Oper. Res. 67(2):577–597.Abstract, Google Scholar
• Baruah S, Haritsa J, Sharma N (1994) On-line scheduling to maximize task completions. 1994 Proc. Real-Time Systems Sympos. (IEEE, San Juan, Puerto Rico), 228–236.Google Scholar
• Bhalgat A, Goel A, Khanna S (2011) Improved approximation results for stochastic knapsack problems. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1647–1665.Google Scholar
• Blado D, Toriello A (2019) Relaxation analysis for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 29(1):1–30.Google Scholar
• Blado D, Hu W, Toriello A (2016) Semi-infinite relaxations for the dynamic knapsack problem with stochastic item sizes. SIAM J. Optim. 26(3):1625–1648.Google Scholar
• Boshuizen FA, Kertz RP (1999) Smallest-fit selection of random sizes under a sum constraint: Weak convergence and moment comparisons. Adv. Appl. Probab. 31(1):178–198.Google Scholar
• Bruss FT, Robertson JB (1991) “Wald’s lemma” for sums of order statistics of i.i.d. random variables. Adv. Appl. Probab. 23(3):612–623.Google Scholar
• Bumpensanti P, Wang H (2020) A re-solving heuristic with uniformly bounded loss for network revenue management. Management Sci. Forthcoming.Google Scholar
• Carraway RL, Schmidt RL, Weatherford LR (1993) An algorithm for maximizing target achievement in the stochastic knapsack problem with normal returns. Naval Res. Logist. 40(2):161–173.Google Scholar
• Cayley A (1875) Mathematical questions and their solutions. Edu. Times 22:18–19.Google Scholar
• Chen L, Homem-de Mello T (2010) Re-solving stochastic programming models for airline revenue management. Ann. Oper. Res. 177(1):91–114.Google Scholar
• Coffman EG Jr, Flatto L, Weber RR (1987) Optimal selection of stochastic intervals under a sum constraint. Adv. Appl. Probab. 19(2):454–473.Google Scholar
• Cooper WL (2002) Asymptotic behavior of an allocation policy for revenue management. Oper. Res. 50(4):720–727.Link, Google Scholar
• Dantzig GB (1957) Discrete-variable extremum problems. Oper. Res. 5(2):266–277.Link, Google Scholar
• Dean BC, Goemans MX, Vondrák J (2004) Approximating the stochastic knapsack problem: The benefit of adaptivity. Proc. 45th Annual IEEE Sympos. Foundations Comput. Sci. (IEEE Press, Piscataway, NJ), 208–217.Google Scholar
• Dean BC, Goemans MX, Vondrák J (2005) Adaptivity and approximation for stochastic packing problems. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 395–404.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
• Derman C, Lieberman GJ, Ross SM (1975) A stochastic sequential allocation model. Oper. Res. 23(6):1120–1130.Link, Google Scholar
• Derman C, Lieberman GJ, Ross SM (1978) A renewal decision problem. Management Sci. 24(5):554–561.Link, Google Scholar
• Gallego G, van Ryzin G (1994) Optimal dynamic pricing of inventories with stochastic demand over finite horizons. Management Sci. 40(8):999–1020.Link, Google Scholar
• Gallego G, van Ryzin G (1997) A multiproduct dynamic pricing problem and its applications to network yield management. Oper. Res. 45(1):24–41.Link, Google Scholar
• Gnedin A, Seksenbayev A (2019) Asymptotics and renewal approximation in the online selection of increasing subsequence. Preprint, submitted April 25, https://arxiv.org/abs/1904.11213.Google Scholar
• Gupta A, Krishnaswamy R, Molinaro M, Ravi R (2011) Approximation algorithms for correlated knapsacks and non-Martingale bandits. Ostrovosky R, ed. 2011 IEEE 52nd Annual Sympos. Foundations Comput. Sci.—FOCS 2011 (IEEE, Piscataway, NJ), 827–836.Google Scholar
• Henig MI (1990) Risk criteria in a stochastic knapsack problem. Oper. Res. 38(5):820–825.Link, Google Scholar
• Ilhan T, Iravani SMR, Daskin MS (2011) Technical note—The adaptive knapsack problem with stochastic rewards. Oper. Res. 59(1):242–248.Link, Google Scholar
• Jasin S, Kumar S (2012) A re-solving heuristic with bounded revenue loss for network revenue management with customer choice. Math. Oper. Res. 37(2):313–345.Link, Google Scholar
• Jasin S, Kumar S (2013) Analysis of deterministic LP-based booking limit and bid price controls for revenue management. Oper. Res. 61(6):1312–1320.Link, Google Scholar
• Kellerer H, Pferschy U, Pisinger D (2004) Knapsack Problems (Springer-Verlag, Berlin).Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms (ACM, New York), 630–631.Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, Google Scholar
• Kleywegt AJ, Papastavrou JD (2001) The dynamic and stochastic knapsack problem with random sized items. Oper. Res. 49(1):26–41.Link, Google Scholar
• Li J, Yuan W (2013). Stochastic combinatorial optimization via Poisson approximation. STOC’13—Proc. 2013 ACM Sympos. Theory Comput. (ACM, New York), 971–980.Google Scholar
• Lueker GS (1998) Average-case analysis of off-line and on-line knapsack problems. J. Algorithms 29(2):277–305.Google Scholar
• Ma W (2018) Improvements and generalizations of stochastic knapsack and Markovian bandits approximation algorithms. Math. Oper. Res. 43(3):789–812.Link, Google Scholar
• Marchetti-Spaccamela A, Vercellis C (1995) Stochastic on-line knapsack problems. Math. Programming 68(1, Ser. A):73–104.Google Scholar
• Martello S, Toth P (1990) Knapsack Problems, Wiley-Interscience Series in Discrete Mathematics and Optimization (John Wiley & Sons Ltd., Chichester, UK).Google Scholar
• Merzifonluoğlu Y, Geunes J, Romeijn HE (2012) The static stochastic knapsack problem with normally distributed item sizes. Math. Programming 134(2, Ser. A):459–489.Google Scholar
• Moser L (1956) On a problem of Cayley. Scripta Mathematica 22:289–292.Google Scholar
• Nakai T (1986) An optimal selection problem for a sequence with a random number of applicants per period. Oper. Res. 34(3):478–485.Link, Google Scholar
• Papastavrou JD, Rajagopalan S, Kleywegt AJ (1996) The dynamic and stochastic knapsack problem with deadlines. Management Sci. 42(12):1706–1718.Link, Google Scholar
• Prastacos GP (1983) Optimal sequential investment decisions under conditions of uncertainty. Management Sci. 29(1):118–134.Link, Google Scholar
• Reiman MI, Wang Q (2008) An asymptotically optimal policy for a quantity-based network revenue management problem. Math. Oper. Res. 33(2):257–282.Link, Google Scholar
• Rhee W, Talagrand M (1991) A note on the selection of random variables under a sum constraint. J. Appl. Probab. 28(4):919–923.Google Scholar
• Samuels SM, Steele JM (1981) Optimal sequential selection of a monotone sequence from a random sample. Ann. Probab. 9(6):937–947.Google Scholar
• Seksenbayev A (2018) Refined asymptotics in the online selection of an increasing subsequence. Preprint, submitted August 18, https://arxiv.org/abs/1808.06300.Google Scholar
• Steele JM (2016) The Bruss-Robertson inequality: Elaborations, extensions, and applications. Math. Appl. (Warsaw) 44(1):3–16.Google Scholar
• Talluri KT, van Ryzin GJ (2004) The Theory and Practice of Revenue Management, International Series in Operations Research & Management Science, vol. 68 (Kluwer Academic Publishers, Boston).Google Scholar
• Vera A, Banerjee S (2019) The Bayesian prophet: A low-regret framework for online decision making. Preprint, submitted January 15, https://arxiv.org/abs/1901.05028.Google Scholar
• Wu H, Srikant R, Liu X, Jiang C (2015) Algorithms with logarithmic or sublinear regret for constrained contextual bandits. Cortes C, Lawrence ND, Lee DD, Sugiyama M, Garnett R, eds. Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits, Advances in Neural Information Processing Systems, vol. 28 (Curran Associates, Inc., Montreal), 433–441.Google Scholar