• Skip to main content
  • Skip to after header navigation
  • Skip to site footer
ERN: Emerging Researchers National Conference in STEM

ERN: Emerging Researchers National Conference in STEM

  • About
    • About AAAS
    • About NSF
    • About the Conference
    • Project Team
    • Advisory Board
  • Conference
  • Abstracts
    • Abstract Submission Process
    • Abstract Submission Guidelines
    • Presentation Guidelines
  • Travel Awards
  • Resources
    • Award Winners
    • Code of Conduct-AAAS Meetings
    • Code of Conduct-ERN Conference
    • Conference Agenda
    • Conference Materials
    • Conference Program Books
    • ERN Photo Galleries
    • Events | Opportunities
    • Exhibitor Info
    • HBCU-UP PI/PD Meeting
    • In the News
    • NSF Harassment Policy
    • Plenary Session Videos
    • Professional Development
    • Science Careers Handbook
    • Additional Resources
    • Archives
  • Engage
    • Webinars
    • ERN 10-Year Anniversary Videos
    • Plenary Session Videos
  • Contact Us
  • Login

Implementation of Improved Parallel Stable Matching Algorithms

Undergraduate #245
Discipline: Computer Sciences and Information Management
Subcategory: Computer Science & Information Systems
Session: 1
Room: Exhibit Hall A

Michael Mandulak - Salisbury University
Co-Author(s): Enyue Lu, Salisbury University, MD



The stable marriage problem, as introduced by Gale and Shapley, poses the question pertaining to the generation of a stable matching between given sets of n men and n women based on 2n ranking lists where each man (woman) ranks each woman (man) based on marital preference. A stable matching is noted as a matching of each man (woman) to a single woman (man) such that no man or woman prefers another partner over their currently matched partner. Gale and Shapley, alongside this problem proposal, introduced an algorithm, the GS algorithm, that guarantees a stable matching with a time complexity of O(n^2). This solution, however, is considered too inefficient for modern applications in networking and the general matching of two sets, leading to explorations in parallel solutions through high-performance computation. Such work has led to algorithms such as the Parallel Iterative Improvement (PII) algorithm and the Convergent Parallel Iterative Improvement (CPII) algorithm, which efficiently provide stable matchings using n^2 processing elements (PEs). While the PII algorithm has results supporting its run time complexity improvement upon the GS algorithm with a logarithmic growth trend, the algorithm faces a cycling issue, reducing the accuracy to approximately 90%. The CPII algorithm, however, claims a run time complexity similar to that of the PII algorithm but with a guarantee of a stable matching in every case. While this claim is assumed from the basis of the PII algorithm, implementation-based results are needed to justify the efficiency and accuracy hypotheses of the CPII algorithm. As such, implementation of both the PII and CPII algorithms was conducted for result verification purposes utilizing C++ and OpenMPI parallelization across a twenty node high-performance computing cluster (approximately four-hundred threads total). Following tests of both algorithms from all n between four and twenty (ten-thousand and two-thousand tests per n, respectively), the resulting before and after time data was graphed and evaluated based on growth trends as n increases. Based on the data, the PII algorithm followed the logarithmic growth trend as expected, while the CPII algorithm also closely followed this logarithmic trend up until n of nineteen, where the time taken to find a stable matching spiked. Due to the nature of run time complexity analysis, it is fair to assume that, since relatively small values of n are being tested, this increase in run time is the starting point for the algorithm’s growth trend, otherwise the n_0 of the time complexity analysis. Despite this run time concern, the data collected supports the notion of the CPII algorithm’s improvement upon the PII algorithm through the guarantee of a stable matching in every case. Future work includes further data collection for the CPII algorithm’?s run time analysis with a more capable high-performance computing cluster in order to exceed the n of twenty maximum placed by the hardware constraints.

Funder Acknowledgement(s): This work is funded by the National Science Foundation under the Research Experience for Undergraduates Program CNS1757017 grant. We would like to thank Professor Matthias K. Gobbert at the University of Maryland, Baltimore County (UMBC) for allowing us to use the UMBC High Performance Computing Facility.

Faculty Advisor: Enyue Lu, ealu@salisbury.edu

Role: For this research project, I have programmed both the PII algorithm and the CPII algorithm in C++ for run time data collection based on the research papers that introduce these algorithms. Similarly, I have written scripts to arbitrarily generate preference lists for testing and to compile resulting time data for graphical representation and statistical analysis. All of this followed the initial steps of research on parallel computation and OpenMPI as well as the history of the stable marriage problem itself.

Sidebar

Abstract Locators

  • Undergraduate Abstract Locator
  • Graduate Abstract Locator

This material is based upon work supported by the National Science Foundation (NSF) under Grant No. DUE-1930047. Any opinions, findings, interpretations, conclusions or recommendations expressed in this material are those of its authors and do not represent the views of the AAAS Board of Directors, the Council of AAAS, AAAS’ membership or the National Science Foundation.

AAAS

1200 New York Ave, NW
Washington,DC 20005
202-326-6400
Contact Us
About Us

  • LinkedIn
  • Facebook
  • Instagram
  • Twitter
  • YouTube

The World’s Largest General Scientific Society

Useful Links

  • Membership
  • Careers at AAAS
  • Privacy Policy
  • Terms of Use

Focus Areas

  • Science Education
  • Science Diplomacy
  • Public Engagement
  • Careers in STEM

Focus Areas

  • Shaping Science Policy
  • Advocacy for Evidence
  • R&D Budget Analysis
  • Human Rights, Ethics & Law

© 2023 American Association for the Advancement of Science