Research Article

Poster: Dynamic and NM1-Right Selection for the Parallel Iterative Improvement Stable Matching Algorithm

Published: 2023-10-23

Journal: Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing

DOI: 10.1145/3565287.3617979

Abstract

Poster: Dynamic and NM1-Right Selection for the Parallel Iterative Improvement Stable Matching Algorithm Authors: Alec Kyritsis, Scott Wynn, Stephora Cesar Alberi, Enyue Lu MobiHoc '23: Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing Pages 568 - 570 https://doi.org/10.1145/3565287.3617979 Published: 16 October 2023 Abstract 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 reduction in complexity. We propose a stable matching algorithm using n2 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 an alternative selection method for pairs in the PII algorithm, called Dynamic Selection, leading to an algorithm that fully converges over 200,000 trials and generally converges much faster. We also suggest the Right-Minimum selection method, leading to an algorithm which converges in approximately 99.9% of cases and can be combined with the PII-SC algorithm's cycle detection and Gale-Shapley Initiation to remove all cycles observed thus far. Index Terms Poster: Dynamic and NM1-Right Selection for the Parallel Iterative Improvement Stable Matching Algorithm Theory of computation Design and analysis of algorithms Parallel algorithms Published In MobiHoc '23: Proceedings of the Twenty-fourth International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing October 2023 Contributors Alec Kyritsis, Middlebury College, Middlebury, Vermont, USA Scott Wynn, University of Washington, Seattle, Seattle, Washington, United States of America Stephora Cesar Alberi, Salisbury University, Salisbury, Maryland, USA Enyue Lu, Salisbury University, Salisbury, Maryland, United States of America Copyright © 2023 Owner/Author(s). Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page.

Faculty Members

  • Stephora Cesar Alberi - Salisbury University, Salisbury, Maryland, USA
  • Alec Kyritsis - Middlebury College, Middlebury, Vermont, USA
  • Enyue Lu - Salisbury University, Salisbury, Maryland, United States of America
  • Scott Wynn - University of Washington, Seattle, Seattle, Washington, United States of America

Themes

  • Parallel computing
  • Stable matching problem
  • Algorithm optimization

Categories

Download Article