Home

The goal of this package is to provide well-tested implementations of polynomial time algorithms for stable matchings problems. For help understanding most of the algorithms presented here, see the Algmatch Webapp which compliments these implementations by providing intuitive visualisations of the algorithms' executions.

Current Polynomial-Time Algorithms:

• SM: Stable Marriage
• HR: Hospital/Residents
  • Resident-optimal algorithm and hospital-optimal algorithm
• SPA-S: Student Project Allocation with lecturer preferences over students
  • Student-optimal algorithm and lecturer-optimal algorithm
• SR: Stable Roommates
• SMT: Strong and Super-stable matchings in Stable Marriage with Ties
• HRT: Hospital/Residents with Ties
  • Strong: Resident-optimal algorithm and hospital-optimal algorithm for strong stability
  • Super: Resident-optimal algorithm and hospital-optimal algorithm for super-stability
• SPA-ST: Student Project Allocation with lecturer preferences over students and ties
  • Super: Student-optimal algorithm

Future Work

1. The research work on the missing variants for SPA-ST is incomplete. These should be relatively easy to add to the current structure.
2. Kavitha et al. improve on the time complexity of the strong stability algorithms here.
3. In the interest of comparing weakly stable solutions to strongly stable ones or super stable ones, it would be useful to add IP models for weak stability and perhaps also the 3/2-approximation algorithm due to Király which usually performs much better than that in practice.