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

Prophet inequalities are a useful tool for designing online allocationprocedures and comparing their performance to the optimal offline allocation.In the basic setting of $k$-unit prophet inequalities, the well-known procedureof Alaei (2011) with its celebrated performance guarantee of$1-\frac{1}{\sqrt{k+3}}$ has found widespread adoption in mechanism design andgeneral online allocation problems in online advertising, healthcarescheduling, and revenue management. Despite being commonly used to deriveapproximately-optimal algorithms for multi-resource allocation problems, thetightness of Alaei's guarantee has remained unknown. In this paper characterizethe tight guarantee in Alaei's setting, which we show is in fact strictlygreater than $1-\frac{1}{\sqrt{k+3}}$ for all $k>1$.  We also consider the more general online stochastic knapsack problem whereeach individual allocation can consume an arbitrary fraction of the initialcapacity. Here we introduce a new ``best-fit'' procedure with a performanceguarantee of $\frac{1}{3+e^{-2}}\approx0.319$, which we also show is tight withrespect to the standard LP relaxation. This improves the previously best-knownguarantee of 0.2 for online knapsack. Our analysis differs from existing onesby eschewing the need to split items into ``large'' or ``small'' based oncapacity consumption, using instead an invariant for the overall utilization ondifferent sample paths. Finally, we refine our technique for the unit-densityspecial case of knapsack, and improve the guarantee from 0.321 to 0.3557 in themulti-resource appointment scheduling application of Stein et al. (2020).

Tight Guarantees for Multi-unit Prophet Inequalities and Online Stochastic Knapsack