LIPIcs.OPODIS.2016.12.pdf
- Filesize: 0.49 MB
- 16 pages
Document
Distributed Stable Matching with Similar Preference Lists
Authors
-
Part of:
Volume:
20th International Conference on Principles of Distributed Systems (OPODIS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Principles of Distributed Systems (OPODIS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2017-04-06
Cite As Get BibTex
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)
https://doi.org/10.4230/LIPIcs.OPODIS.2016.12
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.
Subject Classification
Keywords
- distributed stable matching
- similar preference lists
- stable matching
- stable marriage
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Nir Amira, Ran Giladi, and Zvi Lotker. Distributed Weighted Stable Marriage Problem. In 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Sirince, Turkey, June 2010.
-
Ismel Brito and Pedro Meseguer. Distributed Stable Matching Problems. In 11th International Conference on Principles and Practice of Constraint Programming (CP), Sitges, Spain, October 2005.
-
Ismel Brito and Pedro Meseguer. Distributed stable matching problems with ties and incomplete lists. In 12th International Conference on Principles and Practice of Constraint Programming (CP), Nantes, France, September 2006.
-
Patrik Floréen, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Almost Stable Matchings by Truncating the Gale–Shapley Algorithm. Algorithmica, September 2010.
-
D. Gale and L. S. Shapley. College Admissions and the Stability of Marriage. The American Mathematical Monthly, January 1962.
-
Dan Gusfield and Robert W. Irving. The Stable Marriage Problem: Structure and Algorithms. The MIT Press, 1989.
-
Robert W. Irving, David F. Manlove, and Sandy Scott. The Stable Marriage Problem with Master Preference Lists. Discrete Applied Mathematics, August 2008.
-
Deepak Kapur and Mukkai S. Krishnamoorthy. Worst-case Choice for the Stable Marriage Problem. Information Processing Letters, July 1985.
-
Alex Kipnis and Boaz Patt-Shamir. A Note on Distributed Stable Matching. In 29th IEEE International Conference on Distributed Computing Systems (ICDCS), Montreal, QC, Canada, June 2009.
-
Eyal Kushilevitz. Communication Complexity. In Advances in Computers, volume 44. Elsevier, 1997.
-
Rafail Ostrovsky and Will Rosenbaum. Fast Distributed Almost Stable Matchings. In 34th ACM Symposium on Principles of Distributed Computing (PODC), Donostia-San Sebastián, Spain, July 2015.
-
Michael J. Quinn. A Note on Two Parallel Algorithms to Solve the Stable Marriage Problem. BIT Numerical Mathematics, September 1985.
-
S. S. Tseng and R. C. T. Lee. A Parallel Algorithm to Solve the Stable Marriage Problem. BIT Numerical Mathematics, September 1984.