Improved Paths to Stability for the Stable Marriage Problem
Improved Paths to Stability for the Stable Marriage Problem
复制标题
改善稳定婚姻问题的稳定之路
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Changyong Hu
中科院分区：
文献类型：
--
作者：
V. Garg;Changyong Hu
稳定的婚姻问题要求一个人找到没有阻塞对的婚姻。鉴于不稳定的匹配，罗斯和范德·弗特（Roth and Vande Vate）表明，存在一系列匹配，导致稳定的匹配，通过满足阻止对来获得每个连续的匹配。 Roth和Vande Vate的算法产生的序列长度为$ O（n^3）$，其中$ n $是男人（和女性）的数量。在本文中，我们提出了一种算法，该算法以一系列长度$ o（n^2）$的匹配序列实现稳定性。我们还提供了一种有效的算法，以在匹配之间适当的距离函数下找到最接近给定初始匹配的稳定匹配。
The stable marriage problem requires one to find a marriage with no blocking pair. Given a matching that is not stable, Roth and Vande Vate have shown that there exists a sequence of matchings that leads to a stable matching in which each successive matching is obtained by satisfying a blocking pair. The sequence produced by Roth and Vande Vate's algorithm is of length $O(n^3)$ where $n$ is the number of men (and women). In this paper, we present an algorithm that achieves stability in a sequence of matchings of length $O(n^2)$. We also give an efficient algorithm to find the stable matching closest to the given initial matching under an appropriate distance function between matchings.