SEMINAR: Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples Seminar

Seminar
This event has now finished.
  • Date and time: Wednesday 17 January 2024, 1pm to 2pm
  • Location: In-person only
    A/D271 (above Alcuin Porters)
  • Audience: Open to staff, students
  • Admission: Free admission, booking not required

Event details

Speaker: David Manlove (Glasgow)

Paper: Couples can be tractable

Abstract: 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) 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. We show that our algorithm also implies the polynomial-time solvability of a stable b-matching problem, where the underlying graph is a multigraph with loops.

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. Finally, we show that the problem of finding a matching with the minimum number of blocking pairs in HRC is not approximable within m1−ε, for any ε>0, where m is the total length of the hospitals' preference lists, unless P=NP, even if each couple applies to only one pair of hospitals. Our polynomial-time solvability results greatly expand the class of known tractable instances of HRC and provide additional evidence as to why long-standing entry-level labour markets that allow couples such as the National Resident Matching Program remain successful to this day.

This is joint work with Gergely Csáji, Iain McBride and James Trimble.

Host: Jorgen Kratz (York)