Prophet Secretary for k-Knapsack and l-Matroid Intersection via Continuous Exchange Property

1. Albers, S., Khan, A., Ladewig, L.: Improved online algorithms for knapsack and gap in the random order model. In: Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pp. 22:1–22:23 (2019)

   Google Scholar 

2. Azar, Y., Chiplunkar, A., Kaplan, H.: Prophet secretary: Surpassing the 1-1/e barrier. In: Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 303–318. ACM (2018)

   Google Scholar 

3. Babaioff, M., Immorlica, N., Kempe, D., Kleinberg, R.: A knapsack secretary problem with applications. In: Charikar, M., Jansen, K., Reingold, O., Rolim, J.D.P. (eds.) APPROX/RANDOM -2007. LNCS, vol. 4627, pp. 16–28. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74208-1_2

   Chapter  Google Scholar 

4. Babaioff, M., Immorlica, N., Kleinberg, R.: Matroids, secretary problems, and online mechanisms. In: Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 434–443. Society for Industrial and Applied Mathematics (2007)

   Google Scholar 

5. Brualdi, R.A.: Comments on bases in dependence structures. Bull. Aust. Math. Soc. 1(2), 161–167 (1969)

   Article  MathSciNet  Google Scholar 

6. Correa, J., Foncea, P., Hoeksma, R., Oosterwijk, T., Vredeveld, T.: Posted price mechanisms for a random stream of customers. In: Proceedings of the 2017 ACM Conference on Economics and Computation, pp. 169–186 (2017)

   Google Scholar 

7. Correa, J., Saona, R., Ziliotto, B.: Prophet secretary through blind strategies. In: Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1946–1961. SIAM (2019)

   Google Scholar 

8. Dütting, P., Feldman, M., Kesselheim, T., Lucier, B.: Prophet inequalities made easy: stochastic optimization by pricing non-stochastic inputs. SIAM J. Comput. 49(3), 540–582 (2020)

   Article  MathSciNet  Google Scholar 

9. Dynkin, E.B.: The optimum choice of the instant for stopping a Markov process. Soviet Math. 4, 627–629 (1963)

   MATH  Google Scholar 

10. Ehsani, S., Hajiaghayi, M., Kesselheim, T., Singla, S.: Prophet secretary for combinatorial auctions and matroids. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 700–714. SIAM (2018)

    Google Scholar 

11. Esfandiari, H., Hajiaghayi, M.T., Liaghat, V., Monemizadeh, M.: Prophet secretary. SIAM J. Discrete Math. 31(3), 1685–1701 (2017)

    Article  MathSciNet  Google Scholar 

12. Feldman, M., Svensson, O., Zenklusen, R.: A simple o (log log (rank))-competitive algorithm for the matroid secretary problem. In: Proceedings of the Twenty-sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1189–1201 (2014)

    Google Scholar 

13. Feldman, M., Svensson, O., Zenklusen, R.: Online contention resolution schemes. In: Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1014–1033. SIAM (2016)

    Google Scholar 

14. Kleinberg, R., Matthew, S., Weinberg, M.: prophet inequalities. In: Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, pp. 123–136. ACM (2012)

    Google Scholar 

15. Krengel, U., Sucheston, L.: Semiamarts and finite values. Bull. Am. Math. Soc. 83, 745–747 (1977)

    Article  MathSciNet  Google Scholar 

16. Krengel, U., Sucheston, L.: On semiamarts, amarts, and processes with finite value. Probab. Banach Spaces 4, 197–266 (1978)

    MathSciNet  Google Scholar 

17. Lachish, O.: O (log log rank) competitive ratio for the matroid secretary problem. In: 2014 IEEE 55th Annual Symposium on Foundations of Computer Science, pp. 326–335 (2014)

    Google Scholar 

18. Samuel-Cahn, E.: Comparison of threshold stop rules and maximum for independent nonnegative random variables. Ann. Probab. 12, 1213–1216 (1984)

    Article  MathSciNet  Google Scholar 

Download references