7 citations · 18 across the 15 of their papers we have counts for
Showing 2014 · cs.GTShow all
2 papers · 2 filters
cs.GT2014
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…
cs.GT2014
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…