Submodular Secretary Problem with Shortlists

Understand

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.