Patrik Floréen · Petteri Kaski · Valentin Polishchuk · Jukka Suomela

Almost stable matchings by truncating the Gale–Shapley algorithm

Algorithmica · volume 58, issue 1, pages 102–118, September 2010 · doi:10.1007/s00453-009-9353-9

authors’ version publisher’s version arXiv.org

Abstract

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 + ε)-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.

Links

Conference Version

© Springer 2010 — The original publication is available at www.springerlink.com.

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.