Abstract
In submodular ksecretary 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 ksecretary 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 ksecretary 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 11/eepsilonO(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 ksecretary problem is (1/eO(k^{1/2}))(11/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 kcardinality 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 11/eepsilonO(k^{1}) approximation. This result substantially improves upon [NorouziFard 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].
BibTeX  Entry
@InProceedings{agrawal_et_al:LIPIcs:2018:10094,
author = {Shipra Agrawal and Mohammad Shadravan and Cliff Stein},
title = {{Submodular Secretary Problem with Shortlists}},
booktitle = {10th Innovations in Theoretical Computer Science Conference (ITCS 2019)},
pages = {1:11:19},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770958},
ISSN = {18688969},
year = {2018},
volume = {124},
editor = {Avrim Blum},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2018/10094},
URN = {urn:nbn:de:0030drops100949},
doi = {10.4230/LIPIcs.ITCS.2019.1},
annote = {Keywords: Submodular Optimization, Secretary Problem, Streaming Algorithms}
}
Keywords: 

Submodular Optimization, Secretary Problem, Streaming Algorithms 
Collection: 

10th Innovations in Theoretical Computer Science Conference (ITCS 2019) 
Issue Date: 

2018 
Date of publication: 

08.01.2019 