3 papers
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.DM2023
Computational complexity of -stable matchings
Haris Aziz, Gergely Csáji, Ágnes Cseh
We study deviations by a group of agents in the three main types of matching markets: the house allocation, the marriage, and the roommates models. For a given instance, we call a…
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…