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 classical prophet inequality, a gambler faces a sequence of items,whose values are drawn independently from known distributions. Upon the arrivalof each item, its value is realized and the gambler either accepts it and thegame ends, or irrevocably rejects it and continues to the next item. The goalis to maximize the value of the selected item and compete against the expectedmaximum value of all items. A tight competitive ratio of $\frac{1}{2}$ isestablished in the classical setting and various relaxations have been proposedto surpass the barrier, including the i.i.d. model, the order selection model,and the random order model.  In this paper, we advance the study of the order selection prophetinequality, in which the gambler is given the extra power for selecting thearrival order of the items. Our main result is a $0.725$-competitive algorithm,that substantially improves the state-of-the-art $0.669$ ratio by Correa, Saonaand Ziliotto~(Math. Program. 2021), achieved in the harder random order model.Recently, Agrawal, Sethuraman and Zhang~(EC 2021) proved that the task ofselecting the optimal order is NP-hard. Despite this fact, we introduce a novelalgorithm design framework that translates the discrete order selection probleminto a continuous arrival time design problem. From this perspective, we canfocus on the arrival time design without worrying about the thresholdoptimization afterwards. As a side result, we achieve the optimal $0.745$competitive ratio by applying our algorithm to the i.i.d. model.

Order Selection Prophet Inequality: From Threshold Optimization to Arrival Time Design