Preference swaps for the stable matching problem

DOI10.1016/J.TCS.2022.11.003MaRDI QIDQ2699977zbMATH OpenOpenAlexFDO

Authors Eduard Eiben, G. Gutin, Philip R. Neary, Clément Rambaud, Magnus Wahlström, A. Yeo

Publication date 20 April 2023

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

parameterized complexitystable matchingsubmodular minimizationswaps

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• Stable matching problems with exchange restrictions
• Improving man-optimal stable matchings by minimum change of preference lists
• Hard variants of stable marriage.
• Size Versus Stability in the Marriage Problem
• Size versus stability in the marriage problem

Cites work

• A combinatorial algorithm minimizing submodular functions in strongly polynomial time.
• Bribery and control in stable marriage
• Can you beat treewidth?
• College Admissions and the Stability of Marriage
• Complexity of the Steiner Network Problem with Respect to the Number of Terminals
• Finding stable matchings that are robust to errors in the input
• Graphs and Marriages
• Kernels in perfect line-graphs
• Of Stable Marriages and Graphs, and Strategy and Polytopes
• Parameterized algorithms
• Stable marriage assignment for unequal sets

Cited in

(6)

• Improving man-optimal stable matchings by minimum change of preference lists
• Stability, optimality and manipulation in matching problems with weighted preferences
• Preference Swaps for the Stable Matching Problem
• The complexity of matching games: a survey
• Can you link up with treewidth?
• Can you link up with treewidth?

This page was built for publication: Preference swaps for the stable matching problem

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