The week's pick
Random Articles
Reseach Article
Selection Improvements on the Parallel Iterative Improvement Algorithm for Stable Matching
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 186 - Number 43 |
| Year of Publication: 2024 |
| Authors: Scott Wynn, Alec Kyritsis, Stephora Alberi, Enyue Lu |
10.5120/ijca2024924060
|
Scott Wynn, Alec Kyritsis, Stephora Alberi, Enyue Lu . Selection Improvements on the Parallel Iterative Improvement Algorithm for Stable Matching. International Journal of Computer Applications. 186, 43 ( Sep 2024), 49-56. DOI=10.5120/ijca2024924060
Abstract
Sequential algorithms for the Stable Matching Problem are often too slow in the context of some large scale real-time applications like switch scheduling. Parallel architectures can offer a notable decrease in runtime complexity. This paper proposes a stable matching algorithm that runs in O(nlog(n)) time using n2 processors. The proposed algorithm is structurally based on the Parallel Iterative Improvement (PII) algorithm, where we suggest alternative selection methods for pairs, called Right-Minimum and Dynamic Selection, as well as a faster preprocessing step, called Quick Initialization. The proposed algorithm improves the convergence rate from 90% in the original PII algorithm to 100% in the proposed algorithm over more than 3.6 million trials and significantly improves runtime.
References
- S.T. Cao, L.V. Thanh, and H.H. Viet. Finding Maximum Weakly Stable Matchings for Hospitals/Residents with Ties Problem via Heuristic Search. In AI 2023: Advances in Artificial Intelligence, Lecture Notes in Computer Science. Springer, Singapore, 2024. doi:10.1007/978-981-99-8388- 9 36.
- Kimmo Eriksson and Olle H¨aggstr¨om. Instability of matchings in decentralized markets with various preference structures. International Journal of Game Theory, 36(3–4):409– 420, 2008. doi:10.1007/s00182-007-0110-0.
- T. Feder, N. Megiddo, and S.A. Plotkin. A sublinear parallel algorithm for stable matching. Theoretical Computer Science, 233(1–2):297–308, 2000.
- Enrico Maria Fenoaltea, Izat B. Baybusinov, Jianyang Zhao, Lei Zhou, and Yi-Cheng Zhang. The stable marriage problem: an interdisciplinary review from the physicist’s perspective. Physics Reports, 917:1–79, 2021.
- Patrik Flor´een, Petteri Kaski, Valentin Polishchuk, and Jukka Suomela. Almost stable matchings by truncating the Gale– Shapley algorithm. Algorithmica, 58:102–118, 2010.
- David Gale and Lloyd S. Shapley. College admissions and the stability of marriage. The American Mathematical Monthly, 69(1):9–15, 1962.
- C.C. Huang, T. Kavitha, J. Mestre, and others. On the dynamics of distributed computing and stable matchings. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing (STOC), pages 287–296. ACM, 2007.
- R.W. Irving, P. Leather, and D. Gusfield. An efficient algorithm for the “stable roommates” problem. Journal of the ACM, 34(3):532–543, 1987.
- D.E. Knuth. Mariages Stables. Les Presses de L’Universit´e de Montr´eal, Montr´eal, 1976.
- Alec Kyritsis, Scott Wynn, Stephora Alberi, and Enyue Lu. Dynamic and Right-Minimum Selection for the Parallel Iterative Improvement Stable Matching Algorithm. In Proceedings of Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing (ACM MOBIHOC), series REUNS workshop, pages 568– 570, October 2023. ACM. doi:10.1145/3565287.3617979. Extended Abstract and Poster.
- Enyue Lu, Mei Yang, Yi Zhang, and SQ Zheng. Design and implementation of an acyclic stable matching scheduler. In GLOBECOM’03. IEEE Global Telecommunications Conference (IEEE Cat. No. 03CH37489), volume 7, pages 3938– 3942. IEEE, 2003.
- Enyue Lu and SQ Zheng. A parallel iterative improvement stable matching algorithm. In High Performance Computing- HiPC 2003: 10th International Conference, Hyderabad, India, December 17-20, 2003. Proceedings 10, pages 55–65. Springer, 2003.
- A.E. Roth and J.H. Vande Vate. Random paths to stability in two-sided matching. Econometrica, 58(6):1475–1480, 1990.
- Alvin E. Roth and Elliott Peranson. The NRMP matching algorithm revisited: theory versus practice. Academic Medicine, 70(6):477–484, 1995. URL: https://journals.lww.com/ academicmedicine/abstract/1995/06000/The_NRMP_ matching_algorithm_revisited__theory.8.aspx.
- Youcef Saad and Martin H. Schultz. Data communication in parallel architectures. Parallel Computing, 11(2):131–150, 1989.
- S. Subramanian. A parallel approach to stable marriage problem. Information Processing Letters, 41(5):227–233, 1992.
- Colin White. An Improved Parallel Iterative Algorithm for Stable Matching. SuperComputing 2013, 2013. Extended Abstract and Poster.
- Yuxiang Zhang, Lin Cui, and Yuan Zhang. A stable matching based elephant flow scheduling algorithm in data center networks. Computer Networks, 120:186–197, 2017.
Index Terms
Keywords