4 papers
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…
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…
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…
Solving the Maximum Popular Matching Problem with Matroid Constraints
Gergely Csáji, Tamás Király, Yu Yokoi
We consider the problem of finding a maximum popular matching in a many-to-many matching setting with two-sided preferences and matroid constraints. This problem was proposed by Ka…