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 ...
In the stable marriage problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is ...
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 ...
Association for Computing Machinery
New York, NY, United States
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in