A Self-stabilizing Algorithm for Maximum Popular Matching of Strictly Ordered Preference Lists
Authors: Zhengnan Shi
In this paper, we consider the problem of Popular Matching of strictly ordered preference lists. A Popular Matching is not guaranteed to exist in any network. We propose an IDbased, constant space, self-stabilizing algorithm that converges to a Maximum Popular Matching an optimum solution, if one exist. We show that the algorithm stabilizes in O(n5) moves under any scheduler (daemon).
Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1079514Procedia APA BibTeX Chicago EndNote Harvard JSON MLA RIS XML ISO 690 PDF Downloads 841
 D. J. Abraham, R. W. Irving, T. Kavitha, and K. Mehlhorn. Popular matchings. SIAM J. Comput., 37(4):1030-1045, 2007.
 J. Beauquier, A. K. Datta, M. Gradinariu, and F. Magniette. Selfstabilizing local mutual exclusion and daemon refinement. In International Symposium on Distributed Computing, pages 223-237, 2000.
 E. W. Dijkstra. Self-stabilizing systems in spite of distributed control. Comm. ACM, 17(11):643-644, Jan. 1974.
 S. Dolev. Self-Stabilization. MIT Press, 2000.
 S. Dolev, A. Israeli, and S. Moran. Uniform dynamic self-stabilizing leader election. IEEE Trans. on Parallel and Distributed Systems, 8(4), 1995.
 D. Gale and L. S. Shapley. College admissions and the stability of marriage. American Mathematical Monthly, 69:9-15, 1962.
 P. Gardenfors. Match making: assignments based on bilateral preferences. Behavioral Sciences, 20:166-173, 1975.
 D. Gusfield and R. W. Irving. The Stable Marriage Problem: Structure and Algorithms. MIT Press, 1989.
 P. Hall. On representatives of subsets. Journal of the London Mathematical Society, 10:26-30, 1935.
 S. M. Hedetniemi, S. T. Hedetniemi, D. P. Jacobs, and P. K. Srimani. Self-stabilizing algorithms for minimal dominating sets and maximal independent sets. Comput. Math. Appl., 46(5-6):805-811, 2003.
 S.-C. Hsu and S.-T. Huang. A self-stabilizing algorithm for maximal matching. Inform. Process. Lett., 43:77-81, 1992.
 A. Panconesi and A. Srinivasan. The local nature of -coloring and its algorithmic applications. Combinatorica, 15:225-280, 1995.
 S. Rajagopalan and V. Vazirani. Primal-dual RNC approximation algorithms for set cover and covering integer programs. SIAM J. Comput., 28:525-540, 1998.
 Z. Shi, W. Goddard, and S. T. Hedetniemi. an anonymous selfstabilizing algorithm for 1-maximal independent set in trees. Information Processing Letters, 91(2):77-83, 2004.
 G. Tel. Introduction to Distributed Algorithms, Second Edition. Cambridge University Press, Cambridge UK, 2000.