2026-07-25T14:33:08Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10094 2024-03-06T10:45:22Z ddc:004 open_access

Submodular Secretary Problem with Shortlists Agrawal, Shipra Shadravan, Mohammad Stein, Cliff Submodular Optimization Secretary Problem Streaming Algorithms 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) sized 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 submodular k-secretary problem is (1/e-O(k^{-1/2}))(1-1/e) [Thomas Kesselheim and Andreas Tönnis, 2017]. The proposed algorithm also has significant implications for another important problem of 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 eta_epsilon(k)=O(k) to achieve a 1-1/e-epsilon-O(k^{-1}) approximation. This result substantially improves upon [Norouzi-Fard et al., 2018], which achieved the previously best known approximation factor of 1/2 + 8 x 10^{-14} using O(k log k) memory; and closely matches the known upper bound for this problem [McGregor and Vu, 2017]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shipra Agrawal and Mohammad Shadravan and Cliff Stein 2019 Is Part Of LIPIcs, Volume 124, 10th Innovations in Theoretical Computer Science Conference (ITCS 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2019.1 urn:nbn:de:0030-drops-100949 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2019.1 eng https://creativecommons.org/licenses/by/3.0/legalcode