Selection Improvements for the Parallel Iterative Algorithm for Stable Matching

Sequential algorithms for the Stable Matching Problem are often too slow in the context of some large scale applications like switch scheduling. Parallel architectures can offer a notable decrease in runtime complexity. We propose a stable matching algorithm using n^2 processors that converges in O(nlog(n)) average runtime. The algorithm is structurally based on the Parallel Iterative Improvement (PII) algorithm, which successfully finds a stable matching in approximately 90% of cases. We suggest alternative selection methods for pairs in the PII algorithm, called Right-Minimum and Dynamic Selection, resulting in full convergence over 3.3 million trials and generally much faster termination.