عنوان
پدید آورنده
موضوع
رده
کتابخانه
محل استقرار
TLpq2384799556
انگلیسی
Submodular Secretary Problem with Shortlists under General Constraints
[Thesis]
Shadravan, Mohammad
Stein, Clifford
Columbia University
2020
124
Ph.D.
Columbia University
2020
In submodular usdkusd-secretary problem, the goal is to select usdkusd 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 usdkusd-secretary problem with shortlists. In the proposed problem setting, the algorithm is allowed to choose more than usdkusd items as part of a shortlist. Then, after seeing the entire input, the algorithm can choose a subset of size usdkusd 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 usdkusd-secretary problem. In particular, using an usdO(k)usd 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 usd1-1/e-\epsilon-O(k^{-1})usd competitive ratio for any constant usd\epsilon>0usd, using a shortlist of size usd\eta_{\epsilon}(k)=O(k)usd. Also, for the special case of usdmusd-submodular functions, we demonstrate an algorithm that achieves a usd1-\epsilonusd competitive ratio for any constant usd\epsilon>0usd, using an usdO(1)usd shortlist. Finally, we show that our algorithm can be implemented in the streaming setting using a memory buffer of size usd\eta_{\epsilon}(k)=O(k)usd to achieve a usd1-1/e-\epsilon-O(k^{-1})usd approximation for submodular function maximization in the random order streaming model. This substantially improves upon the previously best known approximation factor of usd1/2 + 8\times 10^{-14}usd [Norouzi-Fard et al. 2018] that used a memory buffer of size usdO(k\log k)usd. We further generalize our results to the case of matroid constraints. We design an algorithm that achieves a usd1/2(1-1/e^2-\epsilon-O(1/k))usd competitive ratio for any constant usd\epsilon>0usd, using a shortlist of size O(k). This is especially surprising considering that the best known competitive ratio for the matroid secretary problem is usdO(\log\log k)usd. An important application of our algorithm is for the random order streaming of submodular functions. We show that our algorithm can be implemented in the streaming setting using usdO(k)usd memory. It achieves a usd1/2(1-1/e^2-\epsilon-O(1/k))usd approximation. The previously best known approximation ratio for streaming submodular maximization under matroid constraint is 0.25 (adversarial order) due to [Feldman et al.], [Chekuri et al.], and [Chakrabarti et al.]. Moreover, we generalize our results to the case of usdpusd-matchoid constraints and give a usd\frac{1}{p+1}(1-1/e^{p+1}-\epsilon-O(1/k))usd approximation using usdO(k)usd memory, which asymptotically approaches the best known offline guarantee usd\frac{1}{p+1}usd [Nemhauser et al.]. Finally we empirically evaluate our results on real world data sets such as YouTube video and Twitter stream.
Computer science
Operations research
Shadravan, Mohammad
Stein, Clifford
مطالعه متن کتاب p
[Thesis]
276903
a
Y
