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 introduce a new approach for designing Random-order Contention ResolutionSchemes (RCRS) via exact solution in continuous time. Given a function$c(y):[0,1] \rightarrow [0,1]$, we show how to select each element whicharrives at time $y \in [0,1]$ with probability exactly $c(y)$. We provide arigorous algorithmic framework for achieving this, which discretizes the timeinterval and also needs to sample its past execution to ensure these exactselection probabilities. We showcase our framework in the context of onlinecontention resolution schemes for matching with random-order vertex arrivals.For bipartite graphs with two-sided arrivals, we design a $(1+e^{-2})/2 \approx0.567$-selectable RCRS, which we also show to be tight. Next, we show that thepresence of short odd-length cycles is the only barrier to attaining a (tight)$(1+e^{-2})/2$-selectable RCRS on general graphs. By generalizing our bipartiteRCRS, we design an RCRS for graphs with odd-length girth $g$ which is$(1+e^{-2})/2$-selectable as $g \rightarrow \infty$. This convergence happensvery rapidly: for triangle-free graphs (i.e., $g \ge 5$), we attain a $121/240+ 7/16 e^2 \approx 0.563$-selectable RCRS. Finally, for general graphs weimprove on the $8/15 \approx 0.533$-selectable RCRS of Fu et al. (ICALP, 2021)and design an RCRS which is at least $0.535$-selectable. Due to the reductionof Ezra et al. (EC, 2020), our bounds yield a $0.535$-competitive(respectively, $(1+e^{-2})/2$-competitive) algorithm for prophet secretarymatching on general (respectively, bipartite) graphs under vertex arrivals.

Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals