文章基本信息

标题：Distributed Stable Matching with Similar Preference Lists
本地全文：下载
作者：Pankaj Khanchandani ; Roger Wattenhofer
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：70
页码：12:1-12:16
DOI：10.4230/LIPIcs.OPODIS.2016.12
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：Consider a complete bipartite graph of 2n nodes with n nodes on each side. In a round, each node can either send at most one message to a neighbor or receive at most one message from a neighbor. Each node has a preference list that ranks all its neighbors in a strict order from 1 to n. We introduce a non-negative similarity parameter D < n for the preference lists of nodes on one side only. For D = 0, these preference lists are same and for D = n-1, they can be completely arbitrary. There is no restriction on the preference lists of the other side. We show that each node can compute its partner in a stable matching by receiving O(n(D + 1)) messages of size O(log n) each. We also show that this is optimal (up to a logarithmic factor) if D is constant.
关键词：distributed stable matching; similar preference lists; stable matching; stable marriage