Stable matchings with covering constraints: a complete computational trichotomy

Analysis of algorithms (68W40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Title not available (Why is that?)
Some remarks on the stable matching problem
Which problems have strongly exponential complexity?
The hospitals/residents problem with lower quotas
Parameterized Algorithms
An $n^{5/2} $ Algorithm for Maximum Matchings in Bipartite Graphs
College Admissions and the Stability of Marriage
The college admissions problem with lower and common quotas
Matching with quorums
Strategyproof matching with regional minimum and maximum quotas
An analysis of the German university admissions system
School choice with controlled choice constraints: hard bounds versus soft bounds
Marriage, honesty, and stability
On the parameterized complexity of multiple-interval graph problems
Matching with slot-specific priorities: Theory
Algorithmics of Matching Under Preferences
Stable matching with couples
Stable assignment with couples: parameterized complexity and local search
Handbook of Computational Social Choice
A matroid approach to stable matchings with lower quotas
Linear FPT reductions and computational lower bounds
``Almost stable matchings in the roommates problem with bounded preference lists
Parameterized complexity and local search approaches for the stable marriage problem with ties
Improving matching under hard distributional constraints
Stable marriage with ties and bounded length preference lists
The stable marriage problem with restricted pairs.
Efficient algorithms for generalized stable marriage and roommates problems
Stable marriage with covering constraints -- a complete computational trichotomy
Stable marriage and roommates problems with restricted edges: complexity and approximability
Matchings with lower quotas: algorithms and complexity
A note on the serial dictatorship with project closures
A Generalized Polymatroid Approach to Stable Matchings with Lower Quotas
Pareto optimal matchings with lower quotas

Cited In (6)

Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective
An algorithm to compute the full set of many-to-many stable matchings.
Popular critical matchings in the many-to-many setting
Perfect matching interdiction problem restricted to a stable vertex
Stable marriage with covering constraints -- a complete computational trichotomy

This page was built for publication: Stable matchings with covering constraints: a complete computational trichotomy

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2309466)