Calum MacRury

In this note, we formulate a “one-sided” version of Wormald’s differential equation method. In the standard “two-sided” method, one is given a family of random variables which evolve over time and which satisfy some conditions including a tight estimate of the expected change in each variable over one time step. These estimates for the expected one-step changes suggest that the variables ought to be close to the solution of a certain system of differential equations, and the standard method concludes that this is indeed the case. We give a result for the case where instead of a tight estimate for each variable’s expected one-step change, we have only an upper bound. Our proof is very simple, and is flexible enough that if we instead assume tight estimates on the variables, then we recover the conclusion of the standard differential equation method.

We consider the classical online bipartite matching problem in the probe-commit model. In this problem, when an online vertex arrives, its edges must be probed to determine if they exist, based on known edge probabilities. A probing algorithm must respect commitment, meaning that if a probed edge exists, it must be used in the matching. Additionally, each online vertex has a patience constraint which limits the number of probes that can be made to its adjacent edges. We introduce a new configuration linear program and use it to establish competitive ratios which depend on the model used to generate the instance graph, and the arrival order of its online vertices.

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.