Complexity study for the robust stable marriage problem

DOI10.1016/J.TCS.2018.12.017MaRDI QIDQ2419115zbMATH OpenOpenAlexWikidataFDO

Authors Mohamed Siala, G. Simonin, Barry O'Sullivan, 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

NP-completenessrobust stable marriagerobustnessSchaefer's dichotomystable matching

Mathematics Subject Classification ID

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

Recommendations

• On the complexity of robust stable marriage
• The stable marriage problem with ties and restricted edges
• Size Versus Stability in the Marriage Problem
• Size versus stability in the marriage problem
• NP-complete stable matching problems

Cites work

• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• College Admissions and the Stability of Marriage
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• Finding stable matchings that are robust to errors in the input
• Group robust stability in matching markets
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems
• On the complexity of robust stable marriage
• Robust and approximately stable marriages under partial information
• Robust stability in matching markets
• Robustness and regularization of support vector machines
• Stable Matching with Uncertain Linear Preferences
• Technical Note—Convex Programming with Set-Inclusive Constraints and Applications to Inexact Linear Programming
• The Complexity of Counting Stable Marriages
• The complexity of satisfiability problems

Cited in

(5)

• On the complexity of robust stable marriage
• An approach to robustness in the stable roommates problem and its comparison with the stable marriage problem
• A formal theory for the complexity class associated with the stable marriage problem
• Online 2-stage stable matching
• Adapting stable matchings to evolving preferences

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2419115)