Distributed Stable Matching Problems
Distributed Stable Matching Problems
复制标题
分布式稳定匹配问题
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
P. Meseguer
中科院分区：
文献类型：
--
作者：
Ismel Brito;P. Meseguer
我们考虑稳定的婚姻问题和稳定的室友问题，这是稳定匹配问题的两种众所周知的类型。它们是组合问题，可以用集中算法在多项式时间内解决。这就需要公开代理人希望保密的偏好列表。为此，我们定义了这些问题的分布式版本，并提供了一种基于约束的方法来解决这些问题，以保持隐私。我们给出了该方法的实证结果。
We consider the Stable Marriage Problem and the Stable Roommates Problem, two well-known types of the general class of Stable Matching Problems. They are combinatorial problems which can be solved by centralized algorithms in polynomial time. This requires to make public lists of preferences which agents would like to keep private. With this aim, we define the distributed version of these problems, and we provide a constraint-based approach that solves them keeping privacy. We give empirical results on the proposed approach.
Supported by the Spanish REPLI project TIC-2002-04470-C03-03.