发帖
雷达卡
摘要翻译：
稳定婚姻(SM)问题有广泛的实际应用，从将住院医生与医院匹配，到将学生与学校匹配，或者更广泛地与任何双边市场匹配。在经典公式中，n个男人和n个女人（通过严格的总顺序）表达他们对另一个性别成员的偏好。解决SM问题意味着找到一个稳定的婚姻，稳定是一个没有嫉妒的概念：没有结婚的男人和女人会更喜欢对方而不是他们的伴侣或单身。我们既考虑了经典的稳定婚姻问题，也考虑了它的一个有用的变体（称为SMTI)，在这种变体中，男人和女人以一个不完全的偏好列表的形式表达他们的偏好，并与另一个性别的一个子集有联系。只允许与出现在这些列表中的人匹配，我们试图找到一个稳定的匹配，尽可能多的人结婚。SM问题是多项式问题，而SMTI问题是NP-hard问题。我们提出通过局部搜索方法来解决这两个问题，利用问题的性质来减小邻域的大小，并有效地进行局部移动。我们通过测量其运行时行为和对所有可能的稳定婚姻的格进行抽样的能力来经验地评估我们的算法对SM问题的求解。对于SMTI问题，我们的算法的步数仅以O（nlog(n))的形式增长，并且它能很好地对所有稳定婚姻集进行采样，因此，我们的算法在运行时的行为和寻找最大基数稳定婚姻的能力两个方面对SMTI问题的算法进行了评估，结果表明，对于SM问题，我们的算法的步数仅以O（nlog(n))的形式增长。此外，尽管SMTI问题存在NP困难，但我们的方法能够解决大问题，快速返回大且通常是最优大小的稳定匹配。
---
英文标题：
《Local search for stable marriage problems》
---
作者：
M. Gelain and M. S. Pini and F. Rossi and K. B. Venable and T. Walsh
---
最新提交年份：
2010
---
分类信息：
一级分类：Computer Science 计算机科学
二级分类：Artificial Intelligence 人工智能
分类描述：Covers all areas of AI except Vision, Robotics, Machine Learning, Multiagent Systems, and Computation and Language (Natural Language Processing), which have separate subject areas. In particular, includes Expert Systems, Theorem Proving (although this may overlap with Logic in Computer Science), Knowledge Representation, Planning, and Uncertainty in AI. Roughly includes material in ACM Subject Classes I.2.0, I.2.1, I.2.3, I.2.4, I.2.8, and I.2.11.
涵盖了人工智能的所有领域，除了视觉、机器人、机器学习、多智能体系统以及计算和语言（自然语言处理），这些领域有独立的学科领域。特别地，包括专家系统，定理证明（尽管这可能与计算机科学中的逻辑重叠），知识表示，规划，和人工智能中的不确定性。大致包括ACM学科类I.2.0、I.2.1、I.2.3、I.2.4、I.2.8和I.2.11中的材料。
--
---
英文摘要：
The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools, or more generally to any two-sided market. In the classical formulation, n men and n women express their preferences (via a strict total order) over the members of the other sex. Solving a SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these lists, an we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We evaluate empirically our algorithm for SM problems by measuring its runtime behaviour and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behaviour and its ability to find a maximum cardinality stable marriage.For SM problems, the number of steps of our algorithm grows only as O(nlog(n)), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages.Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size despite the NP-hardness of this problem.
---
PDF链接：
https://arxiv.org/pdf/1007.0859
京公网安备 11010802022788号
