text: 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.
  @cite_34: Evidence is presented showing that the McVitie and Wilson algorithm to solve the stable marriage problem has a sequential component that is quite large on the average. Hence parallel implementations of the algorithm are likely to achieve only mediocre average case speedup. A corollary result is that an approximate solution with a few unstable pairings can be found much faster than an exact solution.
  @cite_13: In this paper, we propose a new approach, parallel iterative improvement (PII), to solving the stable matching problem. This approach treats the stable matching problem as an optimization problem with all possible matchings forming its solution space. Since a stable matching always exists for any stable matching problem instance, finding a stable matching is equivalent to finding a matching with the minimum number (which is always zero) of unstable pairs. A particular PII algorithm is presented to show the effectiveness of this approach by constructing a new matching from an existing matching and using techniques such as randomization and greedy selection to speedup the convergence process. Simulation results show that the PII algorithm has better average performance compared with the classical stable matching algorithms and converges in n iterations with high probability. The proposed algorithm is also useful for some real-time applications with stringent time constraint.
summary: Several works have addressed the last question with experiments. Quinn @cite_34 observes experimentally that a matching with only a fraction of unstable edges emerges long before the Gale--Shapley algorithm converges. Lu and Zheng @cite_13 propose a parallel algorithm that outperforms the Gale--Shapley algorithm in practice. Theorem gives theoretical support to the findings in Quinn @cite_34 . Theorem also addresses the concern expressed in the conclusions of Lu and Zheng @cite_13 where it is claimed that Most of existing parallel stable matching algorithms cannot guarantee a matching with a small number of unstable pairs within a given time interval.'' Theorem suggests that if the number of acceptable partners for each participant is bounded, the Gale--Shapley algorithm guarantees a small relative number of unstable edges.