**
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(log^{5}n)
communication rounds for * arbitrary* preferences. We also present a faster randomized variant which requires O(log ^{2}n ) 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 |