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/

Zendy Plus

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

Zendy Tools

Zendy Open

The secretary problem became one of the most prominent online selectionproblems due to its numerous applications in online mechanism design. The taskis to select a maximum weight subset of elements subject to given constraints,where elements arrive one-by-one in random order, revealing a weight uponarrival. The decision whether to select an element has to be taken immediatelyafter its arrival. The different applications that map to the secretary problemask for different constraint families to be handled. The most prominent onesare matroid constraints, which both capture many relevant settings and admitstrongly competitive secretary algorithms. However, dealing with more involvedconstraints proved to be much more difficult, and strong algorithms are knownonly for a few specific settings. In this paper, we present a general frameworkfor dealing with the secretary problem over the intersection of severalmatroids. This framework allows us to combine and exploit the large set ofmatroid secretary algorithms known in the literature. As one consequence, weget constant-competitive secretary algorithms over the intersection of anyconstant number of matroids whose corresponding (single-)matroid secretaryproblems are currently known to have a constant-competitive algorithm.Moreover, we show that our results extend to submodular objectives.

A Framework for the Secretary Problem on the Intersection of Matroids