Calum MacRury

We study the performance of sequential contention resolution and matching algorithms on random graphs with vanishing edge probabilities. The regime with vanishing edge probabilities is interesting for several reasons: 1) in applications such as online advertising, an edge represents a customer clicking an ad and the probability of any such event is tiny; 2) in settings where worst-case instances for contention resolution schemes are known, they have vanishing edge probabilities; 3) this is the main regime of interest in the literature on Erdős–Rényi random graphs. When the edges of the graph are processed in an adversarially-chosen order, we derive a new OCRS that is 0.382-selectable, attaining the "independence benchmark" from the literature under the vanishing edge probabilities assumption. Complementary to this positive result, we show that no OCRS can be more than 0.390-selectable, significantly improving upon the upper bound of 0.428 from the literature. Meanwhile, when the edges of the graph are processed in a uniformly random order, we show that the simple greedy CRS which accepts all active and feasible edges is 1/2-selectable. This result is tight due to a known upper bound. Finally, when the algorithm can choose the processing order, we show that a slight tweak to the random order—give each vertex a random priority and process edges in lexicographic order—results in a strictly better OCRS that is 1-log(2-1/e)≈0.510-selectable. Our positive results also apply to online matching on 1-uniform random graphs with vanishing (non-identical) edge probabilities, extending and unifying some results from that literature.

We introduce a new approach for designing Random-order Contention Resolution Schemes (RCRS’s) via exact solution in continuous time. Given a function c(y):[0,1] →[0,1], we show how to select each element which arrives at time y ∈[0,1] with probability \textitexactly c(y). We provide a rigorous algorithmic framework for achieving this, which discretizes the time interval and also needs to sample its past execution to ensure these exact selection probabilities. We showcase our framework in the context of online contention resolution schemes for matching with random-order vertex arrivals. For bipartite graphs with two-sided arrivals, we design a (1+e^-2)/2 ≈0.567-selectable RCRS, which we also show to be tight. Next, we show that the presence 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 bipartite RCRS, we design an RCRS for graphs with odd-length girth g which is (1+e^-2)/2-selectable as g →∞. This convergence happens very rapidly: for triangle-free graphs (i.e., g \ge 5), we attain a 121/240 + 7/16 e^2 ≈0.563-selectable RCRS. Finally, for general graphs we improve on the 8/15 ≈0.533-selectable RCRS of (Fu et al., 2021) and design an RCRS which is at least 0.535-selectable. Due to the reduction of (Ezra et al., 2020), our bounds yield a 0.535-competitive (respectively, (1+e^-2)/2-competitive) algorithm for prophet secretary matching on general (respectively, bipartite) graphs under vertex arrivals.

Online Contention Resolution Schemes (OCRS’s) represent a modern tool for selecting a subset of elements, subject to resource constraints, when the elements are presented to the algorithm sequentially. OCRS’s have led to some of the best-known competitive ratio guarantees for online resource allocation problems, with the added benefit of treating different online decisions – accept/reject, probing, pricing – in a unified manner. This paper analyzes OCRS’s for resource constraints defined by matchings in graphs, a fundamental structure in combinatorial optimization. We consider two dimensions of variants: the elements being presented in adversarial or random order; and the graph being bipartite or general. We improve the state of the art for all combinations of variants, both in terms of algorithmic guarantees and impossibility results. Some of our algorithmic guarantees are best-known even compared to Contention Resolution Schemes that can choose the order of arrival or are offline. All in all, our results for OCRS directly improve the best-known competitive ratios for online accept/reject, probing, and pricing problems on graphs in a unified manner.