Couples Can Be Tractable : New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples

Csáji, Gergely Kál and Manlove, David and McBride, Iain and Trimble, James (2024) Couples Can Be Tractable : New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples. In: Proceedings of the Thirty-ThirdInternational Joint Conference on Artificial Intelligence. IJCAI, California, pp. 2731-2739. ISBN 9781956792041

Preview

Text 0302.pdf - Published Version Download (187kB) | Preview

Abstract

In this paper we study the Hospitals/Residents problem with Couples (HRC), where a solution is a stable matching or a report that none exists. We present a novel polynomial-time algorithm that can find a near-feasible stable matching (adjusting the hospitals' capacities by at most 1) in an HRC instance where the couples' preferences are sub-responsive (i.e., if one member switches to a better hospital, than the couple also improves if the new pair is also acceptable) and sub-complete (i.e., each pair of hospitals that are individually acceptable to both members are jointly acceptable for the couple) by reducing it to an instance of the Stable Fixtures problem. We also present a polynomial-time algorithm for HRC in a sub-responsive, sub-complete instance that is a Dual Market, or where all couples are one of several possible types. Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC.We complement our algorithms with several hardness results. We show that HRC with sub-responsive and sub-complete couples is NP-hard, even with other strong restrictions. We also show that HRC with a Dual Market is NP-hard under several simultaneous restrictions.

Actions (login required)

Edit Item