2009/11/30 by Katarzyna Paluch, Paluch, Katarzyna
Computer Science · Economics, Econometrics and Finance · #Complexity and Algorithms in Graphs #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Game Theory and Voting Systems #Logic, Reasoning, and Knowledge
paper · pdf · doi:10.48550/arxiv.0911.5660
openalex publication_date 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We give a 3/2-approximation algorithm for stable matchings that runs in O(m) time. The previously best known algorithm by McDermid has the same approximation ratio but runs in O(n3/2m) time, where n denotes the number of people and m is the total length of the preference lists in a given instance. Also the algorithm and the analysis are much simpler. We also give the extension of the algorithm for the many-to-many setting. (This is the version of the paper from March 2011)