2026-08-08T22:44:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7081 2024-03-06T10:39:30Z ddc:004 open_access

Distributed Stable Matching with Similar Preference Lists Khanchandani, Pankaj Wattenhofer, Roger distributed stable matching similar preference lists stable matching stable marriage 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj Khanchandani and Roger Wattenhofer 2017 Is Part Of LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.OPODIS.2016.12 urn:nbn:de:0030-drops-70811 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.12 eng https://creativecommons.org/licenses/by/3.0/legalcode