Showing cs.DSShow all
2 papers · 1 filter
cs.DS2025
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…
cs.DS2024
A Simple Algorithm for Dynamic Carpooling with Recourse
Yuval Efron, Shyamal Patel, Cliff Stein
We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph with nodes according to an adaptive adversary. Our…