عنوان

Submodular Secretary Problem with Shortlists under General Constraints

Number

TLpq2384799556

.Language of Text, Soundtrack etc

انگلیسی

Title Proper

Submodular Secretary Problem with Shortlists under General Constraints

General Material Designation

[Thesis]

First Statement of Responsibility

Shadravan, Mohammad

Subsequent Statement of Responsibility

Stein, Clifford

Name of Publisher, Distributor, etc.

Columbia University

Date of Publication, Distribution, etc.

2020

Specific Material Designation and Extent of Item

124

Dissertation or thesis details and type of degree

Ph.D.

Body granting the degree

Columbia University

Text preceding or following the note

2020

Text of Note

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

Electronic name

p

[Thesis]

276903

a

Y