Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

Show simple item record Floréen, Patrik Kaski, Petteri Polishchuk, Valentin Suomela, Jukka 2011-10-11T16:00:01Z 2011-10-11T16:00:01Z 2010
dc.identifier.citation Floréen , P , Kaski , P , Polishchuk , V & Suomela , J 2010 , ' Almost Stable Matchings by Truncating the Gale–Shapley Algorithm ' , Algorithmica , vol. 58 , no. 1 , pp. 102-118 .
dc.identifier.other PURE: 8391333
dc.identifier.other PURE UUID: f4af088a-8a54-46e7-b263-0fbe19e3b909
dc.identifier.other WOS: 000278615500008
dc.identifier.other Scopus: 77953609217
dc.identifier.other ORCID: /0000-0001-7347-0685/work/32017458
dc.description.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. en
dc.format.extent 17
dc.language.iso eng
dc.relation.ispartof Algorithmica
dc.rights.uri info:eu-repo/semantics/openAccess
dc.subject 111 Mathematics
dc.title Almost Stable Matchings by Truncating the Gale–Shapley Algorithm en
dc.type Article
dc.contributor.organization Helsinki Institute for Information Technology
dc.contributor.organization Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
dc.contributor.organization Department of Computer Science
dc.contributor.organization Adaptive Computing research group / Patrik Floreen
dc.contributor.organization Complex Systems Computation Group
dc.description.reviewstatus Peer reviewed
dc.relation.issn 0178-4617
dc.rights.accesslevel openAccess
dc.type.version acceptedVersion

Files in this item

Total number of downloads: Loading...

Files Size Format View
floreen_2010_almost_stable.pdf 251.4Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record