Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)when quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.OPODIS.2016.12
URN: urn:nbn:de:0030-drops-70811
URL: https://drops.dagstuhl.de/opus/volltexte/2017/7081/
Khanchandani, Pankaj ; Wattenhofer, Roger
Distributed Stable Matching with Similar Preference Lists
| pdf-format: |
|
Abstract
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.
BibTeX - Entry
@InProceedings{khanchandani_et_al:LIPIcs:2017:7081,
author = {Pankaj Khanchandani and Roger Wattenhofer},
title = {{Distributed Stable Matching with Similar Preference Lists}},
booktitle = {20th International Conference on Principles of Distributed Systems (OPODIS 2016)},
pages = {12:1--12:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-031-6},
ISSN = {1868-8969},
year = {2017},
volume = {70},
editor = {Panagiota Fatourou and Ernesto Jim{\'e}nez and Fernando Pedone},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/7081},
URN = {urn:nbn:de:0030-drops-70811},
doi = {10.4230/LIPIcs.OPODIS.2016.12},
annote = {Keywords: distributed stable matching, similar preference lists, stable matching, stable marriage}
}
| Keywords: | distributed stable matching, similar preference lists, stable matching, stable marriage | |
| Seminar: | 20th International Conference on Principles of Distributed Systems (OPODIS 2016) | |
| Issue date: | 2017 | |
| Date of publication: | 06.04.2017 |
