8 papers
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…
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…
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…
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 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…