License: 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: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2017/7081/
Go to the corresponding LIPIcs Volume Portal

Khanchandani, Pankaj ; Wattenhofer, Roger

Distributed Stable Matching with Similar Preference Lists

pdf-format:
LIPIcs-OPODIS-2016-12.pdf (0.5 MB)

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
Collection: 20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Issue Date: 2017
Date of publication: 06.04.2017

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI