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