Showing cs.DSShow all
2 papers · 1 filter
cs.DS2023
Couples can be tractable: New algorithms and hardness results for the Hospitals / Residents problem with Couples
Gergely Csáji, David Manlove, Iain McBride +1
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…
cs.DS2023
A Simple 1.5-Approximation Algorithm for a Wide Range of Max-SMTI Problems
Gergely Csáji
We give a simple approximation algorithm for a common generalization of many previously studied extensions of the maximum size stable matching problem with ties. These generalizati…