4 citations · 28 across the 18 of their papers we have counts for
25 papers
Efficient Algorithms for Online Subadditive Combinatorial Allocations
Calum MacRury, Rian Neogi, Kanstantsin Pashkovich +4
For the online combinatorial allocation problem with subadditive valuations, Correa and Cristi (STOC 2023) proved the existence of a -competitive online algorithm, improving on…
Prophet Inequalities and Online Contention Resolution for Matchoids
Calum MacRury, Pranav Nuti, Jan Vondrák
In the classical prophet inequality, an algorithm observes a sequence of random variables with known distributions in an online fashion, and it must select one of the random variab…
Approximation Algorithms for Action-Reward Query-Commit Matching
Mahsa Derakhshan, Andisheh Ghasemi, Calum MacRury
Matching problems under uncertainty arise in applications such as kidney exchange, hiring, and online marketplaces. A decision-maker must sequentially explore potential matches und…
Forward-backward Contention Resolution Schemes for Fair Rationing
Will Ma, Calum MacRury, Cliff Stein
We use contention resolution schemes (CRS) to derive algorithms for the fair rationing of a single resource when agents have stochastic demands. We aim to provide ex-ante guarantee…
Proportionally Fair Matching via Randomized Rounding
Sharmila Duppala, Nathaniel Grammel, Juan Luque +2
Given an edge-colored graph, the goal of the proportional fair matching problem is to find a maximum weight matching while ensuring proportional representation (with respect to the…
Online Matching and Contention Resolution for Edge Arrivals with Vanishing Probabilities
Will Ma, Calum MacRury, Pranav Nuti
We study the performance of sequential contention resolution and matching algorithms on random graphs with vanishing edge probabilities. When the edges of the graph are processed i…
Online Contention Resolution Schemes for Network Revenue Management and Combinatorial Auctions
Will Ma, Calum MacRury, Jingwei Zhang
We study the Network Revenue Management (NRM) and Online Combinatorial Auctions (OCA) problems, in which products composed of up to L resources are allocated in an online fashion.…
Building Hamiltonian Cycles in the Semi-Random Graph Process in Less Than Rounds
Alan Frieze, Pu Gao, Calum MacRury +2
The semi-random graph process is an adaptive random graph process in which an online algorithm is initially presented an empty graph on vertices. In each round, a vertex is…
Random-order Contention Resolution via Continuous Induction: Tightness for Bipartite Matching under Vertex Arrivals
Calum MacRury, Will Ma
We introduce a new approach for designing Random-order Contention Resolution Schemes (RCRS) via exact solution in continuous time. Given a function ,…
Online Bipartite Matching in the Probe-Commit Model
Allan Borodin, Calum MacRury
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…
Extending Wormald's Differential Equation Method to One-sided Bounds
Patrick Bennett, 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 evol…
On (Random-order) Online Contention Resolution Schemes for the Matching Polytope of (Bipartite) Graphs
Calum MacRury, Will Ma, Nathaniel Grammel
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 al…
Sharp Thresholds in Adaptive Random Graph Processes
Calum MacRury, Erlang Surya
The -process is a single player game in which the player is initially presented the empty graph on vertices. In each step, a subset of edges is independently s…
A Fully Adaptive Strategy for Hamiltonian Cycles in the Semi-Random Graph Process
Pu Gao, Calum MacRury, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes
Brian Brubach, Nathaniel Grammel, Will Ma +2
Matching is one of the most fundamental and broadly applicable problems across many domains. In these diverse real-world applications, there is often a degree of uncertainty in the…
Perfect Matchings in the Semi-random Graph Process
Pu Gao, Calum MacRury, Pawel Pralat
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
The Phase Transition of Discrepancy in Random Hypergraphs
Calum MacRury, Tomáš Masařík, Leilani Pai +1
Motivated by the Beck-Fiala conjecture, we study the discrepancy problem in two related models of random hypergraphs on vertices and edges. In the first (edge-independent)…
Prophet Matching Meets Probing with Commitment
Allan Borodin, Calum MacRury, Akash Rakheja
We consider the online stochastic matching problem for bipartite graphs where edges adjacent to an online node must be probed to determine if they exist, based on known edge probab…
Greedy Approaches to Online Stochastic Matching
Allan Borodin, Calum MacRury, Akash Rakheja
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 a…
Hamilton Cycles in the Semi-random Graph Process
Pu Gao, Bogumil Kaminski, Calum MacRury +1
The semi-random graph process is a single player game in which the player is initially presented an empty graph on vertices. In each round, a vertex is presented to the pla…
Bipartite Stochastic Matching: Online, Random Order, and I.I.D. Models
Allan Borodin, Calum MacRury, Akash Rakheja
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 a…
Probabilistically Faulty Searching on a Half-Line
Anthony Bonato, Konstantinos Georgiou, Calum MacRury +1
We study -Faulty Search, a variant of the classic cow-path optimization problem, where a unit speed robot searches the half-line (or -ray) for a hidden item. The searcher is…
Localization Game for Random Graphs
Andrzej Dudek, Sean English, Alan Frieze +2
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 grap…
Probabilistic Zero Forcing on Random Graphs
Sean English, Calum MacRury, Pawel Pralat
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…