Complexity study for the robust stable marriage problem

DOI10.1016/j.tcs.2018.12.017zbMath1425.91344OpenAlexW2908362341WikidataQ128642165 ScholiaQ128642165MaRDI QIDQ2419115

Gilles Simonin, Barry O'Sullivan, Mohamed Siala, Begum Genc

Publication date: 29 May 2019

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://hal.laas.fr/hal-01974431/file/19-TCS.pdf

zbMATH Keywords

robustnessNP-completenessstable matchingrobust stable marriageSchaefer's dichotomy

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Related Items (1)

Online 2-stage stable matching

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Group robust stability in matching markets
• On the complexity of robust stable marriage
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• Robust and approximately stable marriages under partial information
• Stable Matching with Uncertain Linear Preferences
• Robust stability in matching markets
• The Complexity of Counting Stable Marriages
• Algorithmics of Matching Under Preferences
• The complexity of satisfiability problems
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• College Admissions and the Stability of Marriage

This page was built for publication: Complexity study for the robust stable marriage problem