1.7k citations · 1.9k across the 33 of their papers we have counts for
6 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…
Universal Streaming
Vladimir Braverman, Rafail Ostrovsky, Alan Roytman
Given a stream of data, a typical approach in streaming algorithms is to design a sophisticated algorithm with small memory that computes a specific statistic over the streaming da…
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…
Improved Approximation Algorithms for Earth-Mover Distance in Data Streams
Arman Yousefi, Rafail Ostrovsky
For two multisets and of points in , such that , the earth-mover distance (EMD) between and is the minimum cost of a perfect bipartite matching…