1.7k citations · 1.9k across the 33 of their papers we have counts for
Showing cs.CCShow all
2 papers · 1 filter
cs.CC2014★ 5 cited
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…
cs.CC2014★ 1 cited
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…