2025/02/14 by Qiao, Mingda, Zhang, Wei
#Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2502.09834
We study memory-bounded algorithms for the k-secretary problem. The algorithm of Kleinberg (2005) achieves an optimal competitive ratio of 1 - O(1/√(k)), yet a straightforward implementation requires Ω(k) memory. Our main result is a k-secretary algorithm that matches the optimal competitive ratio using O(log k) words of memory. We prove this result by establishing a general reduction from k-secretary to (random-order) quantile estimation, the problem of finding the k-th largest element in a stream. We show that a quantile estimation algorithm with an O(kα) expected error (in terms of the rank) gives a (1 - O(1/k1-α))-competitive k-secretary algorithm with O(1) extra words. We then introduce a new quantile estimation algorithm that achieves an O(√(k)) expected error bound using O(log k) memory. Of independent interest, we give a different algorithm that uses O(√(k)) words and finds the k-th largest element exactly with high probability, generalizing a result of Munro and Paterson (1980).