The stable marriage problem with ties and restricted edges
From MaRDI portal
Publication:783028
DOI10.1016/J.DISOPT.2020.100571zbMATH Open1506.91117arXiv1907.10458OpenAlexW3010061830MaRDI QIDQ783028FDOQ783028
Authors: Ágnes Cseh, Klaus Heeger 
Publication date: 30 July 2020
Published in: Discrete Optimization (Search for Journal in Brave)
Abstract: In the stable marriage problem, a set of men and a set of women are given, each of whom has a strictly ordered preference list over the acceptable agents in the opposite class. A matching is called stable if it is not blocked by any pair of agents, who mutually prefer each other to their respective partner. Ties in the preferences allow for three different definitions for a stable matching: weak, strong and super-stability. Besides this, acceptable pairs in the instance can be restricted in their ability of blocking a matching or being part of it, which again generates three categories of restrictions on acceptable pairs. Forced pairs must be in a stable matching, forbidden pairs must not appear in it, and lastly, free pairs cannot block any matching. Our computational complexity study targets the existence of a stable solution for each of the three stability definitions, in the presence of each of the three types of restricted pairs. We solve all cases that were still open. As a byproduct, we also derive that the maximum size weakly stable matching problem is hard even in very dense graphs, which may be of independent interest.
Full work available at URL: https://arxiv.org/abs/1907.10458
Recommendations
- The stable marriage problem with restricted pairs.
- Stable marriages with restricted pairs
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- The Stable Roommates Problem with Ties
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of satisfiability problems
- College Admissions and the Stability of Marriage
- Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
- College admissions with stable score-limits
- Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
- Title not available (Why is that?)
- Hard variants of stable marriage.
- Two-sided matching with incomplete information about others' preferences
- Stable marriage and indifference
- The structure of stable marriage with indifference
- Title not available (Why is that?)
- XSAT and NAE-SAT of linear CNF classes
- Stable marriage with ties and bounded length preference lists
- The stable marriage problem with restricted pairs.
- An algorithm for a super-stable roommates problem
- Efficient algorithms for generalized stable marriage and roommates problems
- Title not available (Why is that?)
- Mathematical models for stable matching problems with ties and incomplete lists
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Socially stable matchings in the hospitals/residents problem
Cited In (15)
- Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
- Bribery and control in stable marriage
- On the complexity of robust stable marriage
- Stable marriages with forced pairs and forbidden pairs
- Title not available (Why is that?)
- Constrained stable marriage with free edges or few blocking pairs
- Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
- Adapting stable matchings to forced and forbidden pairs
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- Manipulating the outcome of stable marriage and roommates problems
- Stable marriages with restricted pairs
- Of Stable Marriages and Graphs, and Strategy and Polytopes
- Complexity study for the robust stable marriage problem
- Stable marriage and roommates problems with restricted edges: complexity and approximability
- The stable marriage problem with restricted pairs.
This page was built for publication: The stable marriage problem with ties and restricted edges
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q783028)
