Calum MacRury

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.

The D-process is a single player game in which the player is initially presented the empty graph on n vertices. In each step, a subset of edges X is independently sampled according to a distribution D. The player then selects one edge e from X, and adds e to its current graph. For a fixed monotone increasing graph property P, the objective of the player is to force the graph to satisfy P in as few steps as possible. Through appropriate choices of D, the D-process generalizes well-studied adaptive random graph processes, such as the Achlioptas process and the semi-random graph process We prove a sufficient condition for the existence of a sharp threshold for P in the D-process. For the semi-random process, we use this condition to prove the existence of a sharp threshold when P corresponds to being Hamiltonian or to containing a perfect matching. These are the first results for the semi-random graph process which show the existence of a sharp threshold when P corresponds to containing a sparse spanning graph. Using a separate analytic argument, we show that each sharp threshold is of the form CPn for some fixed constant CP>0. This answers two of the open problems proposed by Ben-Eliezer et al. (SODA 2020) in the affirmative. Unlike similar results which establish sharp thresholds for certain distributions and properties, we establish the existence of sharp thresholds without explicitly identifying asymptotically optimal strategies.

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.