# Submodular Secretary Problem with Shortlists

arXiv: https://arxiv.org/abs/1809.05082 · HTML: https://mlsanity.com/paper/1809.05082/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Sep 2018.

## Built on by (most cited first, 1 of 1)

- [Optimal Data Selection: An Online Distributed View](https://mlsanity.com/paper/2201.10547/) (2022)

## Abstract (arXiv)

In submodular k-secretary problem, the goal is to select k items in a randomly ordered input so as to maximize the expected value of a given monotone submodular function on the set of selected items. In this paper, we introduce a relaxation of this problem, which we refer to as submodular k-secretary problem with shortlists. In the proposed problem setting, the algorithm is allowed to choose more than k items as part of a shortlist. Then, after seeing the entire input, the algorithm can choose a subset of size k from the bigger set of items in the shortlist. We are interested in understanding to what extent this relaxation can improve the achievable competitive ratio for the submodular k-secretary problem. In particular, using an O(k) shortlist, can an online algorithm achieve a competitive ratio close to the best achievable online approximation factor for this problem? We answer this question affirmatively by giving a polynomial time algorithm that achieves a 1-1/e-ε -O(k-1) competitive ratio for any constant ε > 0, using a shortlist of size ηε(k) = O(k). Also, for the special case of m-submodular functions, we demonstrate an algorithm that achieves a 1-ε competitive ratio for any constant ε > 0, using an O(1) shortlist. Finally, we show that our algorithm can be implemented in the streaming setting using a memory buffer of size ηε(k) = O(k) to achieve a 1 - 1/e - ε-O(k-1) approximation for submodular function maximization in the random order streaming model. This substantially improves upon the previously best known approximation factor of 1/2 + 8 × 10-14 [Norouzi-Fard et al. 2018] that used a memory buffer of size O(k log k).