International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
|
Volume 186 - Issue 43 |
Published: September 2024 |
Authors: Scott Wynn, Alec Kyritsis, Stephora Alberi, Enyue Lu |
![]() |
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 (September 2024), 49-56. DOI=10.5120/ijca2024924060
@article{ 10.5120/ijca2024924060, author = { Scott Wynn,Alec Kyritsis,Stephora Alberi,Enyue Lu }, title = { Selection Improvements on the Parallel Iterative Improvement Algorithm for Stable Matching }, journal = { International Journal of Computer Applications }, year = { 2024 }, volume = { 186 }, number = { 43 }, pages = { 49-56 }, doi = { 10.5120/ijca2024924060 }, publisher = { Foundation of Computer Science (FCS), NY, USA } }
%0 Journal Article %D 2024 %A Scott Wynn %A Alec Kyritsis %A Stephora Alberi %A Enyue Lu %T Selection Improvements on the Parallel Iterative Improvement Algorithm for Stable Matching%T %J International Journal of Computer Applications %V 186 %N 43 %P 49-56 %R 10.5120/ijca2024924060 %I Foundation of Computer Science (FCS), NY, USA
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.