Stable marriage with covering constraints -- a complete computational trichotomy
From MaRDI portal
Publication:681890
DOI10.1007/978-3-319-66700-3_25zbMATH Open1403.91262arXiv1602.08230OpenAlexW2276917057MaRDI QIDQ681890FDOQ681890
Authors: Matthias Mnich, Ildikó Schlotter 
Publication date: 13 February 2018
Abstract: We consider Stable Marriage with Covering Constraints (SMC): in this variant of Stable Marriage, we distinguish a subset of women as well as a subset of men, and we seek a matching with fewest number of blocking pairs that matches all of the distinguished people. We investigate how a set of natural parameters, namely the maximum length of preference lists for men and women, the number of distinguished men and women, and the number of blocking pairs allowed determine the computational tractability of this problem. Our main result is a complete complexity trichotomy that, for each choice of the studied parameters, classifies SMC as polynomial-time solvable, NP-hard and fixed-parameter tractable, or NP-hard and W[1]-hard. We also classify all cases of one-sided constraints where only women may be distinguished.
Full work available at URL: https://arxiv.org/abs/1602.08230
Recommendations
- Stable matchings with covering constraints: a complete computational trichotomy
- scientific article; zbMATH DE number 45086
- scientific article; zbMATH DE number 2084708
- A formal theory for the complexity class associated with the stable marriage problem
- Lower Bounds for the Stable Marriage Problem and Its Variants
- Approximability results for stable marriage problems with ties.
- Hardness and approximation results for some variants of stable marriage problem
- Better and simpler approximation algorithms for the stable marriage problem
- Better and Simpler Approximation Algorithms for the Stable Marriage Problem
- A tight approximation bound for the stable marriage problem with restricted ties
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)
Cited In (13)
- Envy-free matchings with lower quotas
- Solving hard stable matching problems involving groups of similar agents
- How long does it take for all users in a social network to choose their communities?
- How hard is it to satisfy (almost) all roommates?
- Stable matchings with covering constraints: a complete computational trichotomy
- Parameterized dichotomy of choosing committees based on approval votes in the presence of outliers
- Title not available (Why is that?)
- A formal theory for the complexity class associated with the stable marriage problem
- Constrained stable marriage with free edges or few blocking pairs
- Non-existence of stable social groups in information-driven networks
- How long does it take for all users in a social network to choose their communities?
- Balanced stable marriage: how close is close enough?
- Stable marriage with groups of similar agents
This page was built for publication: Stable marriage 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 Q681890)
