Almost Stable Matchings by Truncating the Gale-Shapley Algorithm

作者：Floreen Patrik; Kaski Petteri; Polishchuk Valentin^*; Suomela Jukka

来源：Algorithmica, 2010, 58(1): 102-118.

DOI：10.1007/s00453-009-9353-9

• Distributed stable matching
• Almost stable matching
• Local algorithms
• Constant-time randomised algorithms

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 epsilon)-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.

• 出版日期2010-9