Fast distributed Almost Stable Matchings
Rafail Ostrovsky, Will Rosenbaum
Abstract:
In their seminal work on the Stable Marriage Problem, Gale and Shapley [4] describe an algorithm which finds a stable matching in O(n 2) communication rounds. Their algorithm has a natural interpretation as a distributed algorithm where each player is represented by a single processor. In this distributed model, Floreen, Kaski, Polishchuk, and Suomela [3] recently showed that for bounded preference lists, terminating the Gale-Shapley Algorithm after a constant number of rounds results in an almost stable matching.In this paper, we describe a new deterministic distributed algorithm which finds an almost stable matching in O(log5n) communication rounds for arbitrary preferences. We also present a faster randomized variant which requires O(log 2n ) rounds. This run-time can be improved to O(1) rounds for "almost regular" (and in particular complete) preferences. To our knowledge, these are the first sub-polynomial round distributed algorithms for any variant of the stable marriage problem with unbounded preferences.
comment: PODC 2015 pp: 101-108
Fetch PDF file of the paper
| Back to Publications List |