The International Conference for High Performance Computing, Networking, Storage and Analysis
An Improved Parallel Iterative Algorithm for Stable Matching.
Authors: Colin R. White (Amherst College), Enyue Lu (Salisbury University)
Abstract: We propose a parallel algorithm for finding a stable matching that converges in O(n log n) average time using n^2 processors. The algorithm is based on the Parallel Iterative Improvement (PII) algorithm, which finds a stable matching with approximately a 90% success rate. Our algorithm, called the PII-SC algorithm, uses a smart initiation method that decreases the number of iterations to find a stable matching, and also applies a cycle detection method to find a stable matching based on patterns in the preference lists. Both methods decrease the number of times it fails to find a stable matching by three orders of magnitude, and when combined, the chance of failure is less than 10^-7.