Almost stable matchings in constant time
| Autor: | Floréen, Patrik, Kaski, Petteri, Polishchuk, Valentin, Suomela, Jukka |
|---|---|
| Rok vydání: | 2008 |
| Předmět: | |
| Zdroj: | Algorithmica 58 (2010) 102-118 |
| Druh dokumentu: | Working Paper |
| DOI: | 10.1007/s00453-009-9353-9 |
| Popis: | 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. This holds even if ties are present in the preference lists. 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. Comment: 20 pages |
| Databáze: | arXiv |
| Externí odkaz: |
|