Local search approaches in stable matching problems

DOI10.3390/A6040591MaRDI QIDQ1736586zbMATH OpenOpenAlexFDO

Authors Mirco Gelain, Maria Silvia Pini, Francesca Rossi, Toby Walsh, Kristen Brent Venable

Publication date 26 March 2019

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a6040591

zbMATH Keywords

samplinglocal searchstable matchingties and incomplete preference lists

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Matching models (91B68)

Recommendations

• Finding large stable matchings
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Hard variants of stable marriage.
• Size Versus Stability in the Marriage Problem
• Linear time local approximation algorithm for maximum stable marriage

Cites work

• scientific article; zbMATH DE number 5764911 (Why is no real title available?)
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• scientific article; zbMATH DE number 3558960 (Why is no real title available?)
• scientific article; zbMATH DE number 1405659 (Why is no real title available?)
• A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
• A 3/2-Approximation Algorithm for General Stable Marriage
• A \(1.875\)-approximation algorithm for the stable marriage problem
• Algorithm Theory - SWAT 2004
• Algorithmics of matching under preferences. With a foreword by Kurt Mehlhorn
• Approximability results for stable marriage problems with ties.
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Better and simpler approximation algorithms for the stable marriage problem
• College Admissions and the Stability of Marriage
• Finding large stable matchings
• Hard variants of stable marriage.
• Improved approximation results for the stable marriage problem
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Random Paths to Stability in Two-Sided Matching
• Randomized approximation of the stable marriage problem
• Size versus stability in the marriage problem
• Stability, optimality and manipulation in matching problems with weighted preferences
• Stable assignment with couples: parameterized complexity and local search
• Three Fast Algorithms for Four Problems in Stable Marriage
• Understanding the generalized median stable matchings

Cited in

(9)

• A local interaction dynamic for the matching problem
• Improving solution times for stable matching problems through preprocessing
• Editorial: Special issue on matching under preferences
• A surgical scheduling method considering surgeons' preferences
• A Local Computation Approximation Scheme to Maximum Matching
• Solving stable matching problems using answer set programming
• scientific article; zbMATH DE number 2084708 (Why is no real title available?)
• Aggregative coarsening for multilevel hypergraph partitioning
• Stability, optimality and manipulation in matching problems with weighted preferences

This page was built for publication: Local search approaches in stable matching problems

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