عنوان

Submodular Secretary Problem with Shortlists under General Constraints

شماره

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