1 Search Results for "Khanchandani, Pankaj"

Document
DOI: 10.4230/LIPIcs.OPODIS.2016.12
Distributed Stable Matching with Similar Preference Lists

Authors: Pankaj Khanchandani and Roger Wattenhofer

Published in: LIPIcs, Volume 70, 20th International Conference on Principles of Distributed Systems (OPODIS 2016)

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.
Cite as

Pankaj Khanchandani and Roger Wattenhofer. Distributed Stable Matching with Similar Preference Lists. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{khanchandani_et_al:LIPIcs.OPODIS.2016.12,
  author =	{Khanchandani, Pankaj and Wattenhofer, Roger},
  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 =	{Fatourou, Panagiota and Jim\'{e}nez, Ernesto and Pedone, Fernando},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2016.12},
  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}
}
  • Refine by Author
  • 1 Khanchandani, Pankaj
  • 1 Wattenhofer, Roger

  • Refine by Classification

  • Refine by Keyword
  • 1 distributed stable matching
  • 1 similar preference lists
  • 1 stable marriage
  • 1 stable matching

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2017

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact