• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>Structural information and communication complexity >Distributed Weighted Stable Marriage Problem
【24h】

Distributed Weighted Stable Marriage Problem

机译：分布式加权稳定婚姻问题

获取原文
获取原文并翻译 | 示例
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

The Stable Matching problem was introduced by Gale and Shapley in 1962. The input for the stable matching problem is a complete bipartite K_(n,n) graph together with a ranking for each node. Its output is a matching that does not contain a blocking pair, where a blocking pair is a pair of elements that are not matched together but rank each other higher than they rank their current mates. In this work we study the Distributed Weighted Stable Matching problem. The input to the Weighted Stable Matching problem is a complete bipartite K_(n,n) graph and a weight function W. The ranking of each node is determined by W, i.e. node v prefers node u over node u2 if W((v, v1)) > W((v, v2)). Using this ranking we can solve the original Stable Matching problem. We consider two different communication models: the billboard model and the full distributed model. In the billboard model, we assume that there is a public billboard and each participant can write one message on it in each time step. In the distributed model, we assume that, each node can send O(log n) bits on each edge of the K_(n,n).In the billboard model we prove a somewhat surprising tight bound: any algorithm that solves the Stable Matching problem requires at least n - 1 rounds. We provide an algorithm that meets this bound. In the distributed communication model we provide an algorithm named intermediation agencies algorithm, in short (IAA), that solves the Distributed Weighted Stable Marriage problem in O(√n) rounds. This is the first sub-linear distributed algorithm that solves some subcase of the general Stable Marriage problem.
机译：稳定匹配问题是由Gale和Shapley于1962年提出的。稳定匹配问题的输入是一个完整的二分K_（n，n）图以及每个节点的排名。其输出是不包含阻塞对的匹配，其中阻塞对是一对未匹配在一起但彼此排名高于当前排名的元素。在这项工作中，我们研究了分布式加权稳定匹配问题。加权稳定匹配问题的输入是一个完整的二分式K_（n，n）图和一个权重函数W.每个节点的排名由W确定，即如果W（（v， v1））> W（（v，v2））。使用此排名，我们可以解决原始的稳定匹配问题。我们考虑两种不同的通信模型：广告牌模型和完全分布式模型。在广告牌模型中，我们假设有一个公共广告牌，每个参与者在每个时间步都可以在上面写一条消息。在分布式模型中，我们假设每个节点都可以在K_（n，n）的每个边缘上发送O（log n）位。在广告牌模型中，我们证明了一个令人惊讶的紧边界：解决稳定匹配的任何算法问题需要至少n-1轮。我们提供了满足此限制的算法。在分布式通信模型中，我们提供了一种称为中介代理算法（IAA）的算法，该算法可解决O（√n）回合中的分布式加权稳定婚姻问题。这是第一个解决一般稳定婚姻问题某些子情形的子线性分布式算法。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号