7 citations · 18 across the 15 of their papers we have counts for
4 papers · 1 filter
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…
A Stable Marriage Requires Communication
Yannai A. Gonczarowski, Noam Nisan, Rafail Ostrovsky +1
The Gale-Shapley algorithm for the Stable Marriage Problem is known to take steps to find a stable marriage in the worst case, but only steps in the average…