Uniformly Bounded Regret in the Multisecretary Problem

References

• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2007) A knapsack secretary problem with applications. Goemans M, Jansen K, Rolim JDP, Trevisan L, eds. Approximation, Randomization Combinatorial Optimization: Algorithms and Techniques, Lecture Notes in Computer Science, vol. 2129 (Springer-Verlag, Berlin, Heidelberg), 16–28.Google Scholar
• Bertsekas D, Shreve S (1978) Stochastic Optimal Control: The Discrete Time Case (Academic Press, New York).Google Scholar
• Billingsley P (1995) Probability and Measure, Wiley Series in Probability and Mathematical Statistics, 3rd ed. (John Wiley & Sons, Inc., New York).Google Scholar
• Boucheron S, Lugosi G, Massart P (2013) Concentration Inequalities (Oxford University Press, Oxford, UK).Google Scholar
• Bramson M, et al.. (2008) Stability of queueing networks. Probab. Surveys 5:169–345.Google Scholar
• Cayley A (1875) Mathematical questions with their solutions. Ed. Times 23:18–19.Google Scholar
• Chow YS, Moriguti S, Robbins H, Samuels SM (1964) Optimal selection based on relative rank (the “secretary problem”). Israel J. Math. 2(2):81–90.Google Scholar
• Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–296.Google Scholar
• Freeman PR (1983) The secretary problem and its extensions: A review. Internat. Statist. Rev. 51(2):189–206.Google Scholar
• Gilbert JP, Mosteller F (1966) Recognizing the maximum of a sequence. J. Amer. Statist. Assoc. 61(313):35–73.Google Scholar
• Hajek B (1982) Hitting-time and occupation-time bounds implied by drift analysis with applications. Adv. Appl. Probab. 14(3):502–525.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
• Kleinberg R (2017) Personal communication with the authors on the regret for the multi-secretary problem with (n,k)-dependent distribution, September 26, 2017.Google Scholar
• Kleywegt AJ, Papastavrou JD (1998) The dynamic and stochastic knapsack problem. Oper. Res. 46(1):17–35.Link, Google Scholar
• Lindley DV (1961) Dynamic programming and decision theory. Appl. Statist. 10(1):39–51.Google Scholar
• Louchard G, Bruss FT (2016) Sequential selection of the κ best out of n rankable objects. Discrete Math. Theor. Comput. Sci. 18(3):13.Google Scholar
• Moser L (1956) On a problem of Cayley. Scripta Mathematica 22(3/4):289–292.Google Scholar
• Ross N (2011) Fundamentals of Stein’s method. Probab. Surveys 8:210–293.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
• 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. Advances in Neural Information Processing Systems (Curran Associates, Red Hook, New York), 433–441.Google Scholar