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

We provide prophet inequality algorithms for online weighted matching ingeneral (non-bipartite) graphs, under two well-studied arrival models, namelyedge arrival and vertex arrival. The weight of each edge is drawn independentlyfrom an a-priori known probability distribution. Under edge arrival, the weightof each edge is revealed upon arrival, and the algorithm decides whether toinclude it in the matching or not. Under vertex arrival, the weights of alledges from the newly arriving vertex to all previously arrived vertices arerevealed, and the algorithm decides which of these edges, if any, to include inthe matching. To study these settings, we introduce a novel unified frameworkof batched prophet inequalities that captures online settings where elementsarrive in batches; in particular it captures matching under the twoaforementioned arrival models. Our algorithms rely on the construction ofsuitable online contention resolution scheme (OCRS). We first extend theframework of OCRS to batched-OCRS, we then establish a reduction from batchedprophet inequality to batched OCRS, and finally we construct batched OCRSs withselectable ratios of 0.337 and 0.5 for edge and vertex arrival models,respectively. Both results improve the state of the art for the correspondingsettings. For the vertex arrival, our result is tight. Interestingly, apricing-based prophet inequality with comparable competitive ratios is unknown.

Online Stochastic Max-Weight Matching: prophet inequality for vertex and edge arrival models