Optimal $k$-Secretary with Logarithmic Memory

Mingda Qiao, Wei Zhang

We study memory-bounded algorithms for the $k$-secretary problem. The algorithm of Kleinberg (SODA 2005) achieves an optimal competitive ratio of $1-O(1/\sqrt{k})$, yet a straigh…