The problem of Hospitals/Residents with Ties (HRT) broadens the traditional many-to-one matching model by permitting non-strict preference rankings. In this study, we investigate the MAX-HRT variant, whose objective is to identify the largest weakly stable allocation, a problem that has been proven to be NP-hard. To cope with this computational challenge, we design a stochastic optimization scheme that initializes with a random feasible matching and progressively refines it through iterative stability adjustments. During refinement, the method strategically eliminates unstable pair configurations, giving higher priority to unfilled hospitals and unmatched residents to improve convergence efficiency. Experimental results conducted on reference datasets of substantial scale demonstrate that our algorithm reliably yields larger weakly stable matchings while significantly reducing runtime when compared with advanced adaptive-search and hospital-oriented techniques.
BalasundaramH.KrishnashreeJ. B.LimayeG.NasreM. (2025). Stability notions for hospital residents with sizes. In Proceedings of the 45th IARCS annual conference on foundations of software technology and theoretical computer science (FSTTCS 2025) (Vol. 360, pp. 11:1–11:18). LIPIcs.
2.
CsájiG.KirályT.YokoiY. (2025). A simple 1.5-approximation algorithm for a wide range of maximum-size stable matching problems. Mathematics of Operations Research. Epub ahead of print 2025. https://doi.org/10.1287/moor.2024.0725
3.
GaleD.ShapleyL. S. (1962). College admissions and the stability of marriage. The American Mathematical Monthly, 69(1), 9–15.
4.
GelainM.PiniM. S.RossiF.VenableK. B.WalshT. (2010). Local search for stable marriage problems with ties and incomplete lists. In Proceedings of 11th Pacific rim international conference on artificial intelligence (pp. 64–75). Daegu, Korea.
5.
GelainM.PiniM. S.RossiF.VenableK. B.WalshT. (2013). Local search approaches in stable matching problems. Algorithms, 6(4), 591–617.
6.
GentI. P.ProsserP. (2002). An empirical study of the stable marriage problem with ties and incomplete lists. In Proceedings of the 15th European conference on artificial intelligence (pp. 141–145). Lyon, France.
7.
IrvingR. W.ManloveD. F. (2009). Finding large stable matchings. Journal of Experimental Algorithmics, 14(2), 1.2–1.2:30.
8.
IrvingR. W.ManloveD. F.ScottS. (2000). The hospitals/residents problem with ties. In Proceedings of the 7th scandinavian workshop on algorithm theory (pp. 259–271). Bergen, Norway.
9.
IrvingR. W.ManloveD. F.ScottS. (2008). The stable marriage problem with master preference lists. Discrete Applied Mathematics, 156(15), 2959–2977.
10.
IwamaK.MiyazakiS. (2008). A survey of the stable marriage problem and its variants. In Proceedings of the international conference on informatics education and research for knowledge-circulating society (pp. 131–136). Washington, DC, USA.
11.
IwamaK.MiyazakiS.MoritaY.ManloveD. (1999). Stable marriage with incomplete lists and ties. In Proceedings of international colloquium on automata, languages, and programming (pp. 443–452). Prague, Czech Republic.
12.
KirályZ. (2013). Linear time local approximation algorithm for maximum stable marriage. Algorithms, 6(1), 471–484.
13.
KwanashieA.ManloveD. F. (2013). An integer programming approach to the hospitals/residents problem with ties. In Proceedings of the international conference on operations research (pp. 263–269). Erasmus University Rotterdam.
14.
ManloveD. F. (2008). The hospitals/Residents problem. In M. Y. Kao (Eds), Encyclopedia of algorithms. Boston, MA: Springer.
15.
ManloveD. F.IrvingR. W.IwamaK.MiyazakiS.MoritaY. (2002). Hard variants of stable marriage. Theoretical Computer Science, 276(1-2), 261–279.
16.
MuneraD.DiazD.AbreuS.RossiF.SaraswatV.CodognetP. (2015). A local search algorithm for SMTI and its extension to HRT problems. In Proceedings of the 3rd international workshop on matching under preferences (pp. 66–77). Glasgow, United Kingdom.
17.
MuneraD.DiazD.AbreuS.RossiF.SaraswatV.CodognetP. (2015). Solving hard stable matching problems via local search and cooperative parallelization. In Proceedings of the Twenty-Ninth AAAI conference on artificial intelligence (pp. 1212–1218). Austin, Texas.
18.
PetterssonW.DelormeM.GarciaS.GondzioJ.KalcsicsJ.ManloveD. (2021). Improving solution times for stable matching problems through preprocessing. Computers & Operations Research, 128, 105128.
19.
QiuJ. (2024). A tie-breaking based local search algorithm for stable matching problems. preprint, arXiv:2409.10575.
20.
RanjanK.NasreM.NimbhorkarP. (2025). Optimal capacity modification for stable matchings with ties. In Proceedings of the Thirty-Fourth international joint conference on artificial intelligence (IJCAI-25) (pp. 4023–4031). International Joint Conferences on Artificial Intelligence Organization.
21.
RothA. E. (1984). The evolution of the labor market for medical interns and residents: A case study in game theory. Journal of Political Economy, 92(6), 991–1016.
22.
UyenN. T.GiangN. L.NguyenT. T.VietH. H. (2020). A min-conflicts algorithm for maximum stable matchings of the hospitals/residents problem with ties. In Proceedings of 2020 RIVF international conference on computing and communication technologies (pp. 1–6). Ho Chi Minh City, Vietnam.
