Stable marriage with covering constraints -- a complete computational trichotomy

DOI10.1007/978-3-319-66700-3_25zbMath1403.91262arXiv1602.08230OpenAlexW2276917057MaRDI QIDQ681890

Matthias Mnich, Ildikó Schlotter

Publication date: 13 February 2018

Full work available at URL: https://arxiv.org/abs/1602.08230

zbMATH Keywords

matchingstable marriagecomplete complexity trichotomycovering constraints

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (12)

Unnamed Item ⋮ Constrained stable marriage with free edges or few blocking pairs ⋮ Non-existence of stable social groups in information-driven networks ⋮ Stable marriage with groups of similar agents ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ How hard is it to satisfy (almost) all roommates ⋮ Envy-free matchings with lower quotas ⋮ Balanced stable marriage: how close is close enough? ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ Unnamed Item ⋮ Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers ⋮ How long does it take for all users in a social network to choose their communities?

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