Submodular Secretary Problem with Shortlists
share
In , 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 . 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 . In particular, using an O(k) shortlist, can an online algorithm achieve a competitive ratio close to the best achievable offline approximation factor for this problem? We answer this question affirmatively by giving a polynomial time algorithm that achieves a 1-1/e-epsilon-O(k^-1) competitive ratio for any constant epsilon>0, using a shortlist of size eta_epsilon(k)=O(k). This is especially surprising considering that the best known competitive ratio (in polynomial time) for the is (1/e-O(k^-1/2))(1-1/e) kesselheim. Further, for the special case of m-submodular functions, we demonstrate an algorithm that achieves 1-epsilon competitive ratio for any constant epsilon>0, using an O(1) shortlist. For submodular function maximization under random order streaming model and k-cardinality constraint, 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. This substantially improves upon norouzi, which achieved the previously best known approximation factor of 1/2 + 8× 10^-14 using O(k k) memory.
READ FULL TEXT