Research
Working Papers
2024
2024
2023
2023
Accepted Papers
2024
2024
- Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex ArrivalsCalum MacRury, and Will MaIn Annual ACM Symposium on Theory of Computing, STOC , 2024
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.
2023
2023
- Sharp Thresholds in Adaptive Random Graph ProcessesCalum MacRury, and Erlang SuryaRandom Structures and Algorithms, RSA, 2023
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.
- Optimizing Transport Frequency in Multi-Layered Urban Transportation Networks for Pandemic PreventionCalum MacRury, Nykyta Polituchyi , Paweł Prałat , Kinga Siuta , and 1 more authorPublic Transport, 2023
In this paper, we identify determinants of pandemic spread in urban populations. Specifically, we develop a multi-agent simulation framework to model virus spread in complex networks. Our agents periodically commute between home and work via a combination of walking routes and public transit, and make decisions intelligently based upon their location, available routes, and expectations of public transport arrival times. Our infection scheme allows for different contagiousness levels, as a function of the virus’s strain and where the agents interact (i.e., inside or outside). Our results show that the pandemic’s scale is heavily impacted by the network’s structure, and the decision making of the agents. In particular, the progression of the pandemic greatly differs when agents primarily infect each other in a crowded urban transportation system, opposed to while walking. Additionally, the results show that local subgraph characteristics, including topology, structure, and statistics such as its degree distribution and density, affect the viruses’ transmission rates. We also assess the effect of modifying the public transport’s running frequency on the spread of two different virus strains (with different levels of contagiousness). In particular, lowering the running frequency can discourage agents from taking public transportation too often, especially for shorter distances. On the other hand, the low frequency contributes to more crowded streetcars or subway cars if the policy is not designed correctly, which is why such an analysis may prove valuable for finding “sweet spots” that optimize the system. The proposed approach has been validated on real world data, and a model of the transportation network of downtown Toronto. The framework used is flexible and can be easily adjusted to model other urban environments, and additional forms of transportation (such as carpooling, ride-share and more).
- On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) GraphsCalum MacRury, Will Ma , and Nathaniel GrammelIn ACM-SIAM Symposium on Discrete Algorithms, SODA , 2023Major revision at Operations Research
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.
- The Phase Transition of Discrepancy in Random HypergraphsCalum MacRury, Tomáš Masařík , Leilani Pai , and Xavier Pérez-GiménezSIAM Journal on Discrete Mathematics, 2023
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on n vertices and m edges. In the first (\em edge-independent) model, a random hypergraph H_1 is constructed by fixing a parameter p and allowing each of the n vertices to join each of the m edges independently with probability p. In the parameter range in which pn →∞and pm →∞, we show that with high probability (\whp) H_1 has discrepancy at least Ω(2^-n/m \sqrtpn) when m = O(n), and at least Ω(\sqrtpn \logγ) when m ≫n, where γ= \min{ m/n, pn}. In the second (\em edge-dependent) model, d is fixed and each vertex of H_2 independently joins exactly d edges uniformly at random. We obtain analogous results for this model by generalizing the techniques used for the edge-independent model with p=d/m. Namely, for d →∞and dn/m →∞, we prove that \whp H_2 has discrepancy at least Ω(2^-n/m \sqrtdn/m) when m = O(n), and at least Ω(\sqrt(dn/m) \logγ) when m ≫n, where γ=\min{m/n, dn/m}. Furthermore, we obtain nearly matching asymptotic upper bounds on the discrepancy in both models (when p=d/m), in the dense regime of m ≫n. Specifically, we apply the partial colouring lemma of Lovett and Meka to show that \whp H_1 and H_2 each have discrepancy O( \sqrtdn/m \log(m/n)), provided d →∞, d n/m →∞and m ≫n. This result is algorithmic, and together with the work of Bansal and Meka characterizes how the discrepancy of each random hypergraph model transitions from Θ(\sqrtd) to o(\sqrtd) as m varies from m=Θ(n) to m ≫n.
2022
2022
- A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph ProcessPu Gao , Calum MacRury, and Paweł PrałatIn RANDOM , 2022
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamiltonian cycle in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves it in αn rounds, where α< 2.01678 is derived from the solution to some system of differential equations. We also show that the player cannot achieve the desired property in less than βn rounds, where β> 1.26575. These results improve the previously best known bounds and, as a result, the gap between the upper and lower bounds is decreased from 1.39162 to 0.75102.
- Prophet Matching in the Probe-Commit ModelAllan Borodin , Calum MacRury, and Akash RakhejaIn APPROX , 2022
We consider the online bipartite stochastic matching problem with known i.d. (independently distributed) online vertex arrivals. In this problem, when an online vertex arrives, its weighted edges must be probed (queried) to determine if they exist, based on known edge probabilities. Our algorithms operate in the probe-commit model, in that if a probed edge exists, it must be used in the matching. Additionally, each online node has a downward-closed probing constraint on its adjacent edges which indicates which sequences of edge probes are allowable. Our setting generalizes the commonly studied patience (or timeout) constraint which limits the number of probes that can be made to an online node’s adjacent edges. Most notably, this includes non-uniform edge probing costs (specified by knapsack/budget constraint). We extend a recently introduced configuration LP to the known i.d. setting, and also provide the first proof that it is a relaxation of an optimal offline probing algorithm (the offline adaptive benchmark). Using this LP, we establish new competitive bounds all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty).
- Perfect Matchings in the Semi-random Graph ProcessPu Gao , Calum MacRury, and Paweł PrałatSIAM Journal on Discrete Mathematics, 2022
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a perfect matching in as few rounds as possible. In particular, we present an adaptive strategy for the player which achieves a perfect matching in βn rounds, where the value of β< 1.206 is derived from a solution to some system of differential equations. This improves upon the previously best known upper bound of (1+2/e+o(1)) \,n < 1.736 \,n rounds. We also improve the previously best lower bound of (\ln 2 + o(1)) \,n > 0.693 \,n and show that the player cannot achieve the desired property in less than αn rounds, where the value of α> 0.932 is derived from a solution to another system of differential equations. As a result, the gap between the upper and lower bounds is decreased roughly four times.
- Algorithms for p-Faulty Search on a Half-LineAnthony Bonato , Konstantinos Georgiou , Calum MacRury, and Paweł PrałatAlgorithmica, 2022Conference version appeared in LATIN 2020
We study p-Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or 1-ray) for a hidden item. The searcher is probabilistically faulty, and detection of the item with each visitation is an independent Bernoulli trial whose probability of success p is known. The objective is to minimize the worst case expected detection time, relative to the distance of the hidden item to the origin. A variation of the same problem was first proposed by Gal in 1980. Then in 2003, Alpern and Gal [The Theory of Search Games and Rendezvous] proposed a so-called monotone solution for searching the line (2-rays); that is, a trajectory in which the newly searched space increases monotonically in each ray and in each iteration. Moreover, they conjectured that an optimal trajectory for the 2-rays problem must be monotone. We disprove this conjecture when the search domain is the half-line (1-ray). We provide a lower bound for all monotone algorithms, which we also match with an upper bound. Our main contribution is the design and analysis of a sequence of refined search strategies, outside the family of monotone algorithms, which we call t-sub-monotone algorithms. Such algorithms induce performance that is strictly decreasing with t, and for all p ∈(0,1). The value of t quantifies, in a certain sense, how much our algorithms deviate from being monotone, demonstrating that monotone algorithms are sub-optimal when searching the half-line.
- Localization Game for Random GraphsAndrzej Dudek , Sean English , Alan Frieze , Calum MacRury, and 1 more authorDiscrete Applied Mathematics, 2022
We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter ζ(G) for a given graph G is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of ζ(G). Moreover, we extend the argument to sparse graphs.
- Hamilton Cycles in the Semi-random Graph ProcessPu Gao , Bogumił Kamiński , Calum MacRury, and Paweł PrałatEuropean Journal of Combinatorics, 2022
The semi-random graph process is a single player game in which the player is initially presented an empty graph on n vertices. In each round, a vertex u is presented to the player independently and uniformly at random. The player then adaptively selects a vertex v, and adds the edge uv to the graph. For a fixed monotone graph property, the objective of the player is to force the graph to satisfy this property with high probability in as few rounds as possible. We focus on the problem of constructing a Hamilton cycle in as few rounds as possible. In particular, we present a novel strategy for the player which achieves a Hamiltonian cycle in c∗n rounds, where the value of c∗ is the result of a high dimensional optimization problem. Numerical computations indicate that c∗<2.61135. This improves upon the previously best known upper bound of 3n rounds. We also show that the previously best lower bound of (ln2+ln(1+ln2)+o(1))n is not tight.
2021
2021
- Secretary Matching Meets Probing with CommitmentAllan Borodin , Calum MacRury, and Akash RakhejaIn APPROX , 2021
Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one-sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist based on edge probabilities that become known when an online vertex arrives. If a probed edge exists, it must be used in the matching (if possible). We consider the competitiveness of online algorithms in both the adversarial order model (AOM) and the random order model (ROM). More specifically, we consider a bipartite stochastic graph G = (U,V,E) where U is the set of offline vertices, V is the set of online vertices and G has edge probabilities (p_e)_e ∈E and edge weights (w_e)_e ∈E. Additionally, G has probing constraints (\scrC_v)_v ∈V, where \scrC_v indicates which sequences of edges adjacent to an online vertex v can be probed. We assume that U is known in advance, and that \scrC_v, together with the edge probabilities and weights adjacent to an online vertex are only revealed when the online vertex arrives. This model generalizes the various settings of the classical bipartite matching problem, and so our main contribution is in making progress towards understanding which classical results extend to the stochastic probing model.
- Probabilistic Zero Forcing on Random GraphsSean English , Calum MacRury, and Paweł PrałatEuropean Journal of Combinatorics, 2021
Zero forcing is a deterministic iterative graph coloring process in which vertices are colored either blue or white, and in every round, any blue vertices that have a single white neighbor force these white vertices to become blue. Here we study probabilistic zero forcing, where blue vertices have a non-zero probability of forcing each white neighbor to become blue. We explore the propagation time for probabilistic zero forcing on the Erdős-Réyni random graph G(n,p) when we start with a single vertex colored blue. We show that when p=\log^-o(1)n, then with high probability it takes (1+o(1))\log_2 \log_2 n rounds for all the vertices in G(n,p) to become blue, and when \log n/n ≪p \le \log^-O(1) n, then with high probability it takes Θ(\log(1/p)) rounds.
- Zero Forcing Number of Random Regular GraphsDeepak Bal , Patrick Bennett , Sean English , Calum MacRury, and 1 more authorJournal of Combinatorics, 2021
The zero forcing process is an iterative graph colouring process in which at each time step a coloured vertex with a single uncoloured neighbour can force this neighbour to become coloured. A zero forcing set of a graph is an initial set of coloured vertices that can eventually force the entire graph to be coloured. The zero forcing number is the size of the smallest zero forcing set. We explore the zero forcing number for random regular graphs, improving on bounds given by Kalinowski, Kamc̆ev and Sudakov. We also propose and analyze a degree greedy algorithm for finding small zero forcing sets using the differential equations method.
2018
2018
- The Robot Crawler Graph ProcessAnthony Bonato , Rita M. del Río-Chanona , Calum MacRury, Jake Nicolaidis , and 3 more authorsDiscrete Applied Mathematics, 2018Conference version appeared in WAW 2015
Information gathering by crawlers on the web is of practical interest. We consider a simplified model for crawling complex networks such as the web graph, which is a variation of the robot vacuum edge-cleaning process of Messinger and Nowakowski. In our model, a crawler visits nodes via a deterministic walk determined by their weightings which change during the process deterministically. The minimum, maximum, and average time for the robot crawler to visit all the nodes of a graph is considered on various graph classes such as trees, multi-partite graphs, binomial random graphs, and graphs generated by the preferential attachment model.
- Distribution of Coefficients of Rank Polynomials for Random Sparse GraphsDmitry Jakobson , Calum MacRury, Sergey Norin , and Lise TurnerThe Electronic Journal of Combinatorics, 2018
We study the distribution of coefficients of rank polynomials of random sparse graphs. We first discuss the limiting distribution for general graph sequences that converge in the sense of Benjamini-Schramm. Then we compute the limiting distri-bution and Newton polygons of the coefficients of the rank polynomial of randomd-regular graphs.
Unpublished Papers and Technical Notes
2020
2020
- Bipartite Stochastic Matching: Online, Random Order, and I.I.D. ModelsAllan Borodin , Calum MacRury, and Akash Rakheja2020Earlier version of “Prophet Matching in the Probe-Commit Model” and “Secretary Matching Meets Probing with Commitment”.
Within the context of stochastic probing with commitment, we consider the online stochastic matching problem; that is, the one sided online bipartite matching problem where edges adjacent to an online node must be probed to determine if they exist, based on known edge probabilities. If a probed edge exists, it must be used in the matching (if possible). We study this problem in the generality of a patience (or budget) constraint which limits the number of probes that can be made to edges adjacent to an online node. The patience constraint results in modelling and computational efficiency issues that are not encountered in the special cases of unit patience and full (i.e., unlimited) patience. The stochastic matching problem leads to a variety of settings. Our main contribution is to provide a new LP relaxation and a unified approach for establishing new and improved competitive bounds in three different input model settings (namely, adversarial, random order, and known i.i.d.). In all these settings, the algorithm does not have any control on the ordering of the online nodes. We establish competitive bounds in these settings, all of which generalize the standard non-stochastic setting when edges do not need to be probed (i.e., exist with certainty). All of our competitive ratios hold for arbitrary edge probabilities and patience constraints: (1) A 1−1/e ratio when the stochastic graph is known, offline vertices are weighted and online arrivals are adversarial. (2) A 1−1/e ratio when the stochastic graph is known, edges are weighted, and online arrivals are given in random order (i.e., in ROM, the random order model). (3) A 1−1/e ratio when online arrivals are drawn i.i.d. from a known stochastic type graph and edges are weighted. (4) A (tight) 1/e ratio when the stochastic graph is unknown, edges are weighted and online arrivals are given in random order.
2016
2016
- Injective Colouring of Binomial Random GraphsRita M. Rı́o-Chanona , Calum MacRury, Jake Nicolaidis , Xavier Pérez-Giménez , and 2 more authors2016
The injective chromatic number of a graph G is the minimum number of colours needed to colour the vertices of G so that two vertices with a common neighbour receive distinct colours. In this paper, we investigate the injective chromatic number of the binomial random graph G(n, p) for a wide range of p. We also study a natural generalization of this graph parameter for the same model of random graphs.