The stable marriage problem with ties and restricted edges

DOI10.1016/J.DISOPT.2020.100571MaRDI QIDQ783028zbMATH OpenOpenAlexFDO

Authors Ágnes Cseh, Klaus Heeger

Publication date 30 July 2020

Published in Discrete Optimization (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexitystable matchingsrestricted edges

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Matching models (91B68)

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.

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

• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1962834 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• scientific article; zbMATH DE number 7561396 (Why is no real title available?)
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• An algorithm for a super-stable roommates problem
• College Admissions and the Stability of Marriage
• College admissions with stable score-limits
• Efficient algorithms for generalized stable marriage and roommates problems
• Hard variants of stable marriage.
• Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
• Mathematical models for stable matching problems with ties and incomplete lists
• Socially stable matchings in the hospitals/residents problem
• Stable marriage and indifference
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Stable marriage with ties and bounded length preference lists
• The complexity of satisfiability problems
• The stable marriage problem with restricted pairs.
• The structure of stable marriage with indifference
• Two-sided matching with incomplete information about others' preferences
• XSAT and NAE-SAT of linear CNF classes

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
• Constrained stable marriage with free edges or few blocking pairs
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• Computing relaxations for the three-dimensional stable matching problem with cyclic preferences
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Adapting stable matchings to forced and forbidden pairs
• Stable marriages with restricted pairs
• Manipulating the outcome of stable marriage and roommates problems
• 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)