5 citations · 7 across the 4 of their papers we have counts for
4 papers
With Great Speed Come Small Buffers: Space-Bandwidth Tradeoffs for Routing
Avery Miller, Boaz Patt-Shamir, Will Rosenbaum
We consider the Adversarial Queuing Theory (AQT) model, where packet arrivals are subject to a maximum average rate and burstiness . In this model, we analyze th…
It's Not Easy Being Three: The Approximability of Three-Dimensional Stable Matching Problems
Rafail Ostrovsky, Will Rosenbaum
In 1976, Knuth asked if the stable marriage problem (SMP) can be generalized to marriages consisting of 3 genders. In 1988, Alkan showed that the natural generalization of SMP to 3…
Fast distributed almost stable marriages
Rafail Ostrovsky, Will Rosenbaum
In their seminal work on the Stable Marriage Problem, Gale and Shapley describe an algorithm which finds a stable matching in communication rounds. Their algorithm has a n…
On The Communication Complexity of Finding an (Approximate) Stable Marriage
Rafail Ostrovsky, Will Rosenbaum
In this paper, we consider the communication complexity of protocols that compute stable matchings. We work within the context of Gale and Shapley's original stable marriage proble…