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 consider Bayesian online selection problem of a matching in bipartitegraphs, i.e., online weighted matching problem with edge arrivals where onlinealgorithm knows distributions of weights, that corresponds to the intersectionof two matroids in [Kleinberg and Wienberg STOC 12] model. We consider a simpleclass of non adaptive vertex-additive policies that assign static prices to allvertices in the graph and accept each edge only if its weight exceeds the sumof the prices of the edge's endpoints. We show existence of a vertex-additivepolicy with the expected payoff of at least one third of the prophet's payoffand present gradient decent type algorithm that quickly converges to thedesired vector of vertex prices. This improves the adaptive online policy of[Kleinberg and Wienberg STOC 12] for the intersection of two matroids in twoways: our policy is non adaptive and has better approximation guarantee of $3$instead of previous guarantee of $5.82$ against the prophet. We give acomplementary lower bound of $2.25$ for any online algorithm in the bipartitematching setting.

Prophet inequality for bipartite matching: merits of being simple and non adaptive