Almost Stable Matchings by Truncating the Gale–Shapley Algorithm

Visa fullständig post



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 .

Titel: Almost Stable Matchings by Truncating the Gale–Shapley Algorithm
Författare: Floréen, Patrik; Kaski, Petteri; Polishchuk, Valentin; Suomela, Jukka
Upphovmannens organisation: Helsinki Institute for Information Technology
Finnish Centre of Excellence in Algorithmic Data Analysis Research (Algodan)
Department of Computer Science
Adaptive Computing research group / Patrik Floreen
Complex Systems Computation Group
Datum: 2010
Språk: eng
Sidantal: 17
Tillhör serie: Algorithmica
ISSN: 0178-4617
Permanenta länken (URI):
Abstrakt: 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.
Subject: 111 Mathematics
Referentgranskad: Ja
Användningsbegränsning: openAccess
Parallelpublicerad version: acceptedVersion

Filer under denna titel

Totalt antal nerladdningar: Laddar...

Filer Storlek Format Granska
floreen_2010_almost_stable.pdf 251.4Kb PDF Granska/Öppna

Detta dokument registreras i samling:

Visa fullständig post