Finding Robust Solutions to Stable Marriage
Finding Robust Solutions to Stable Marriage
复制标题
寻找稳定婚姻的稳健解决方案
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
G. Simonin
中科院分区：
文献类型：
--
作者：
Begum Genc;M. Siala;B. O’Sullivan;G. Simonin
我们研究了稳定匹配问题中鲁棒性的概念。我们首先通过引入（a，B）-超匹配来定义鲁棒性。一个$（a，B）$-超匹配是一个稳定的匹配，如果$a$对分手，有可能找到另一个稳定的匹配，通过改变这些$a$对和最多$B$其他对的合作伙伴。在这种情况下，我们定义的最强大的稳定匹配作为一个$（1，B）$-超匹配，其中B是最小的。我们发现，检查是否一个给定的稳定匹配是一个$（1，B）$超匹配可以在多项式时间内完成。接下来，我们使用这个程序来设计一个约束规划模型，一个局部搜索方法，和一个遗传算法来找到最强大的稳定匹配。我们对大型实例的经验评估表明，局部搜索优于其他方法。
We study the notion of robustness in stable matching problems. We first define robustness by introducing (a,b)-supermatches. An $(a,b)$-supermatch is a stable matching in which if $a$ pairs break up it is possible to find another stable matching by changing the partners of those $a$ pairs and at most $b$ other pairs. In this context, we define the most robust stable matching as a $(1,b)$-supermatch where b is minimum. We show that checking whether a given stable matching is a $(1,b)$-supermatch can be done in polynomial time. Next, we use this procedure to design a constraint programming model, a local search approach, and a genetic algorithm to find the most robust stable matching. Our empirical evaluation on large instances show that local search outperforms the other approaches.