Fast distributed almost stable marriages
Fast distributed almost stable marriages
复制标题
快速分配几乎稳定的婚姻
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Will Rosenbaum
中科院分区：
文献类型：
--
作者：
R. Ostrovsky;Will Rosenbaum
在他们关于稳定婚姻问题的开创性工作中，Gale 和 Shapley 描述了一种算法，该算法可以在 $O(n^2)$ 通信轮次中找到稳定的匹配。他们的算法有一个自然的解释：分布式算法，其中每个玩家都由单个处理器代表。在这个分布式模型中，Floreen、Kaski、Polishchuk 和 Suomela 最近表明，对于有界偏好列表，在恒定轮数后终止 Gale-Shapley 算法会导致几乎稳定的匹配。在本文中，我们描述了一种新的确定性分布式算法，该算法在 $O(\log^5 n)$ 通信轮次中针对任意偏好找到几乎稳定的匹配。我们还提出了一种更快的随机变体，需要 $O(\log^2 n)$ 轮。对于“几乎常规”（尤其是完整的）偏好，此运行时间可以改进为 $O(1)$ 轮。据我们所知，这是第一个针对具有无限偏好的稳定婚姻问题的任何变体的次多项式轮分布式算法。
In their seminal work on the Stable Marriage Problem, Gale and Shapley 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 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.