A Simple O(log log(rank))-Competitive Algorithm for the Matroid Secretary Problem

References

• Azar PD, Kleinberg R, Weinberg SM (2014) Prophet inequalities with limited information. Chekuri C, ed. Proc. 25th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’14 (SIAM, Philadelphia), 1358–1377.Google Scholar
• Babaioff M, Immorlica N, Kleinberg R (2007) Matroids, secretary problems, and online mechanisms. Bansal N, Pruhs K, Stein C, eds. Proc. 18th Annual ACM-SIAM Sympos. Discrete Algorithms, SODA ’07, 434–443.Google Scholar
• Babaioff M, Immorlica N, Kempe D, Kleinberg R (2008) Online auctions and generalized secretary problems. SIGecom Exchanges 7(2):7:1–7:11.Crossref, Google Scholar
• Barman S, Umboh S, Chawla S, Malec D (2012) Secretary problems with convex costs. Proc. 35th Internat. Colloquium on Automata, Languages and Programming (ICALP): Part I (Springer, Berlin), 75–87.Google Scholar
• Bateni M, Hajiaghayi M, Zadimoghaddam M (2013) Submodular secretary problem and extensions. ACM Trans. Algorithms 9(4):32:1–32:23.,Crossref, Google Scholar
• Chakraborty S, Lachish O (2012) Improved competitive ratio for the matroid secretary problem. Rabani Y, ed. Proc. 23rd Annual ACM-SIAM Sympos. Discrete Algorithms SODA ’12 (SIAM, Philadelphia), 1702–1712.Google Scholar
• Dimitrov NB, Plaxton CG (2012) Competitive weighted matching in transversal matroids. Algorithmica 62(1):333–348.Crossref, Google Scholar
• Dinitz M, Kortsarz G (2014) Matroid secretary for regular and decomposable matroids. SIAM J. Comput. 43(5):1807–1830.Crossref, Google Scholar
• Dynkin EB (1963) The optimum choice of the instant for stopping a Markov process. Soviet Math., Doklady 4.Google Scholar
• Feldman M, Naor J, Schwartz R (2011) Improved competitive ratios for submodular secretary problems. Goldberg LA, Jansen K, Ravi R, Rolim JDP, eds. Proc. 14th Internat. Workshop and 15th Internat. Workshop on Approximation, Randomization, Combin. Optim. Algorithms and Techniques APPROX/RANDOM ’11 (Springer, Berlin), 218–229.Google Scholar
• Ferguson TS (1989) Who solved the secretary problem? Statist. Sci. 4(3):282–296.Crossref, Google Scholar
• Gardner M (1960a) Mathematical games column. Sci. Amer. 202(2):150–154.Crossref, Google Scholar
• Gardner M (1960b) Mathematical games column. Sci. Amer. 202(3):172–182.Crossref, Google Scholar
• Gupta A, Roth A, Schoenebeck G, Talwar K (2010) Constrained non-monotone submodular maximization: Offline and secretary algorithms. Proc. 6th Internat. Conf. Internet and Network Econom. WINE ’10 (Springer, Berlin), 246–257.Google Scholar
• Im S, Wang Y (2011) Secretary problems: Laminar matroid and interval scheduling. Randall D, ed. Proc. 22nd Annual ACM-SIAM Sympos. Discrete Algorithms SODA ’11 (SIAM, Philadelphia), 1265–1274.Google Scholar
• Jaillet P, Soto JA, Zenklusen R (2013) Advances on matroid secretary problems: Free order model and laminar case. Proc. 16th Internat. Conf. Integer Programming Combin. Optim. IPCO ’13 (Springer, Berlin), 254–265.Google Scholar
• Kesselheim T, Radke K, Tönnis A, Vöcking B (2013) An optimal online algorithm for weighted bipartite matching and extensions to combinatorial auctions. Bodlaender HL, Italiano GF, eds. Proc. 21st Eur. Sympos. Algorithms ESA ’13 (Springer, Berlin), 589–600.Google Scholar
• Kleinberg R (2005) A multiple-choice secretary algorithm with applications to online auctions. Proc. 16th Annual ACM-SIAM Sympos. Discrete Algorithms SODA ’05 (SIAM, Philadelphia), 630–631.Google Scholar
• Korula N, Pál M (2009) Algorithms for secretary problems on graphs and hypergraphs. Albers S, marchetti-Spaccamela A, Matias Y, Nikoletseas S, Thomas W, eds. Proc. 36th Internat. Colloquium on Automata, Languages and Programming ICALP ’09, Part II (Springer, Berlin), 508–520.Google Scholar
• Lachish O (2014) O(log log rank) competitive-ratio for the matroid secretary problem. Proc. 55th IEEE Annual Sympos. Foundations Comput. Sci. FOCS ’14 (IEEE Computer Society, Washington, DC), 326–335.Google Scholar
• Lindley DV (1961) Dynamic programming and decision theory. J. Roy. Statist. Soc. Ser. C (Appl. Statist.) 10(1):39–51.Crossref, Google Scholar
• Ma T, Tang B, Wang Y (2016) The simulated greedy algorithm for several submodular matroid secretary problems. Theory Comput. Syst. 58(4):681–706.Crossref, Google Scholar
• Oveis Gharan S, Vondrák J (2013) On variants of the matroid secretary problem. Algorithmica 67(4):472–497.Crossref, Google Scholar
• Schrijver A (2003) Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin).Google Scholar
• Soto JA (2013) Matroid secretary problem in the random-assignment model. SIAM J. Comput. 42(1):178–211.Crossref, Google Scholar