English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the matroid secretary problem, the elements of a matroid $\mathcal{M}$arrive in random order. Once we observe an item we need to irrevocably decidewhether or not to accept it. The set of selected elements should form anindependent set of the matroid. The goal is to maximize the total sum of thevalues assigned to these elements.  We introduce a version of this problem motivated by the shortlist model in[Agrawal et al.]. In this setting, the algorithm is allowed to choose a subsetof items as part of a shortlist, possibly more than $k=rk(\mathcal{M})$ items.Then, after seeing the entire input, the algorithm can choose an independentsubset from the shortlist. Furthermore we generalize the objective function toany monotone submodular function. Is there an online algorithm achieve aconstant competitive ratio using a shortlist of size $O(k)$? We design analgorithm that achieves a $\frac{1}{2}(1-1/e^2-\epsilon-O(1/k))$ competitiveratio for any constant $\epsilon>0$, using a shortlist of size $O(k)$. This isespecially surprising considering that the best known competitive ratio for thematroid secretary problem is $O(\log \log k)$.  An important application of our algorithm is for the random order streamingof submodular functions. We show that our algorithm can be implemented in thestreaming setting using $O(k)$ memory. It achieves a$\frac{1}{2}(1-1/e^2-\epsilon-O(1/k))$ approximation. The previously best knownapproximation ratio for streaming submodular maximization under matroidconstraint is 0.25 (adversarial order) due to [Feldman et al.], [Chekuri etal.], and [Chakrabarti et al.]. Moreover, we generalize our results to the caseof p-matchoid constraints and give a$\frac{1}{p+1}(1-1/e^{p+1}-\epsilon-O(1/k))$ approximation using $O(k)$ memory,which asymptotically approaches the best known offline guarantee$\frac{1}{p+1}$ [Nemhauser et al.]

Submodular Matroid Secretary Problem with Shortlists