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

We give a $0.5368$-competitive algorithm for edge-weighted online bipartitematching. Prior to our work, the best competitive ratio was $0.5086$ due toFahrbach, Huang, Tao, and Zadimoghaddam (FOCS 2020). They achieved theirbreakthrough result by developing a subroutine called \emph{online correlatedselection} (OCS) which takes as input a sequence of pairs and selects one itemfrom each pair. Importantly, the selections the OCS makes are negativelycorrelated.  We achieve our result by defining \emph{multiway} OCSes which receivearbitrarily many elements at each step, rather than just two. In addition tobetter competitive ratios, our formulation allows for a simpler reduction fromedge-weighted online bipartite matching to OCSes. While Fahrbach et al. used afactor-revealing linear program to optimize the competitive ratio, our analysisdirectly connects the competitive ratio to the parameters of the multiway OCS.Finally, we show that the formulation of Farhbach et al. can achieve acompetitive ratio of at most $0.5239$, confirming that multiway OCSes arestrictly more powerful.

Multiway Online Correlated Selection