David F. Manlove

Couples can be Tractable: New Algorithms and Hardness Results for the Hospitals/Residents Problem with Couples

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, where hospitals’ capacities are adjusted by at m...