We show that the ratio of matched individuals to blocking pairs grows linearly with the number of propose–accept rounds executed by the Gale–Shapley algorithm for the stable marriage problem. Consequently, the participants can arrive at an almost stable matching even without full information about the problem instance; for each participant, knowing only its local neighbourhood is enough. In distributed-systems parlance, this means that if each person has only a constant number of acceptable partners, an almost stable matching emerges after a constant number of synchronous communication rounds. We apply our results to give a distributed (2+e)-approximation algorithm for maximum-weight matching in bicoloured graphs and a centralised randomised constant-time approximation scheme for estimating the size of a stable matching.
Our centralised constant-time approximation algorithm in Theorem is based on the ideas of Parnas and Ron @cite_9 and Nguyen and Onak @cite_21 . Their work presents constant-time approximation algorithms for estimating the size of a maximal matching, maximum-cardinality matching, and maximum-weight matching. Our work complements this line of research by presenting an algorithm for estimating the size of a stable matching.
@cite_9 @cite_21
2768321248 2019340823
We present a simple randomized reduction from fully-dynamic integral matching algorithms to fully-dynamic approximately-maximal" fractional matching algorithms. Applying this reduction to the recent fractional matching algorithm of Bhattacharya, Henzinger, and Nanongkai (SODA 2017), we obtain a novel result for the integral problem. Specifically, our main result is a randomized fully-dynamic @math -approximate integral matching algorithm with small polylog worst-case update time. For the @math -approximation regime only a fractional fully-dynamic @math -matching algorithm with worst-case polylog update time was previously known, due to (SODA 2017). Our algorithm is the first algorithm that maintains approximate matchings with worst-case update time better than polynomial, for any constant approximation ratio. We give a 3 2 -approximation algorithm for finding stable matchings that runs in O(m) time. The previous most well-known algorithm, by McDermid, has the same approximation ratio but runs in O(n3 2m) time, where n denotes the number of people andm is the total length of the preference lists in a given instance. In addition, the algorithm and the analysis are much simpler. We also give the extension of the algorithm for computing stable many-to-many matchings.