Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.07467 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909295471230976 |
|---|---|
| author | Wynn, Scott Kyritsis, Alec Alberi, Stephora Lu, Enyue |
| author_facet | Wynn, Scott Kyritsis, Alec Alberi, Stephora Lu, Enyue |
| contents | 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(n log(n))$ average runtime. The algorithm is structurally based on the Parallel Iterative Improvement (PII) algorithm, where we improve the convergence rate from $90\%$ to $100\%$ over a large number of trials. We suggest alternative selection methods for pairs in the PII algorithm, called Right-Minimum and Dynamic Selection, as well as a faster preprocessing step, called Quick Initialization, resulting in full convergence over $3.6$ million trials and significantly improved runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_07467 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Selection Improvements on the Parallel Iterative Algorithm for Stable Matching Wynn, Scott Kyritsis, Alec Alberi, Stephora Lu, Enyue Data Structures and Algorithms 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(n log(n))$ average runtime. The algorithm is structurally based on the Parallel Iterative Improvement (PII) algorithm, where we improve the convergence rate from $90\%$ to $100\%$ over a large number of trials. We suggest alternative selection methods for pairs in the PII algorithm, called Right-Minimum and Dynamic Selection, as well as a faster preprocessing step, called Quick Initialization, resulting in full convergence over $3.6$ million trials and significantly improved runtime. |
| title | Selection Improvements on the Parallel Iterative Algorithm for Stable Matching |
| topic | Data Structures and Algorithms |
| url | https://arxiv.org/abs/2401.07467 |