A Study Of Stable Marriage Problems With Ties
A Study Of Stable Marriage Problems With Ties
复制标题
关系稳定婚姻问题研究
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Scott
中科院分区：
文献类型：
--
作者：
S. Scott
我们研究了稳定婚姻问题的一些变体。这类问题由来已久，但近年来，随着人们研究了在偏好列表中允许领带出现的各种可能性，人们对这类问题的兴趣激增。将关系纳入偏好列表会产生三种不同版本的稳定性，即所谓的超稳定、强稳定和弱稳定。这三个版本的研究提出了许多具有挑战性的问题，本文在其中一些领域贡献了一系列新的成果。我们研究的第一个变体是医院/住院医生的关系问题，这是稳定婚姻问题的多对一变体。我们提出了两种不同的多项式时间算法来寻找强稳定匹配，一种有利于居民，另一种有利于医院。我们还研究了稳定婚姻问题的非二部变体——带Ties的稳定室友问题，并再次提出了寻找强稳定匹配的多项式时间算法。然后，我们介绍了Stable Fixtures问题，这是Stable舍友问题的多对多变体，我们最初关注的是偏好严格的版本。我们提出了一种算法，该算法在输入大小上呈时间线性运行，以寻找稳定的匹配。然后，我们考虑在偏好列表中允许联系时的问题，并提出一种算法，输入大小也是线性的，以找到一个超稳定的匹配。我们还研究了带关系的稳定婚姻问题（SMT）的超稳定匹配集的结构。我们将旋转的概念（本质上是稳定匹配之间的最小差值）推广到超稳定，并证明我们可以构造一个有向无环图来表示这些元旋转之间的优先级。然后，我们利用这个结构证明了我们可以在多项式时间内找到一个平均的超稳定匹配，一个最小遗憾的超稳定匹配和所有的超稳定对，并在连续匹配之间生成所有的多项式时间的超稳定匹配。然后，我们探讨了在弱稳定性中出现的一些问题，其中一些关键问题已知是np困难的。我们展示了在SMT实例中弱稳定匹配的大小和强稳定匹配的大小之间的关系，并且在许多其他变体中也是如此。给出了一种改进的近似算法
We study a number of variants of the Stable Marriage problem. Such problems have a long history, but there has been an upsurge in interest in recent years as the various possibilities that arise when ties are allowed in preference lists have been studied. The inclusion of ties in preference lists gives rise to three different versions of stability, so-called super-stability, strong stability and weak stability. The study of these three versions has thrown up a number of challenging problems, and this thesis contributes a range of new results in some of these areas. The first variant that we study is the Hospitals/Residents problem with ties, a manyto-one variant of the Stable Marriage problem. We present two different polynomial-time algorithms for finding a strongly stable matching, one favouring the residents and the other the hospitals. We also study the Stable Roommates problem with Ties, a non-bipartite variant of the Stable Marriage problem, and we again present a polynomial-time algorithm for finding a strongly stable matching. We then introduce the Stable Fixtures problem, a many-to-many variant of the Stable Roommates problem, initially focusing on the version in which preferences are strict. We present an algorithm, which runs in time linear in the input size, to find a stable matching. We then consider the problem when ties are allowed in the preference lists, and we present an algorithm, again linear in the input size, to find a super-stable matching. We also study the structure underlying the set of super-stable matchings for the Stable Marriage problem with ties (SMT). We extend the concept of a rotation, essentially the minimum difference between stable matchings, to super-stability, and show that we can construct a directed acyclic graph to represent precedence amongst these meta-rotations. We then use this structure to show that we can find an egalitarian super-stable matching, a minimum regret super-stable matching and all the super-stable pairs in polynomialtime, and generate all the super-stable matchings with polynomial-time between successive matchings. We then explore some of the issues arising in weak stability, where a number of the key problems are known to be NP-hard. We show a relationship between the sizes of weakly stable matchings and the size of a strongly stable matching in an instance of SMT, and also in a number of the other variants. We give an improved approximation algorithm