Stable marriage with covering constraints -- a complete computational trichotomy

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

Matthias Mnich, Ildikó Schlotter

Publication date: 13 February 2018

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

zbMATH Keywords

matching; stable marriage; complete complexity trichotomy; covering constraints

Mathematics Subject Classification ID

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

91B68: Matching models