Fast distributed almost stable matchings

DOI10.1145/2767386.2767424MaRDI QIDQ2796247zbMATH OpenOpenAlexWikidataFDO

Authors Rafail Ostrovsky, Will Rosenbaum

Publication date 23 March 2016

Published in Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.2782

zbMATH Keywords

approximation algorithmsdistributed algorithmsstable marriage problemstable matchings

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Distributed algorithms (68W15) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: In their seminal work on the Stable Marriage Problem, Gale and Shapley describe an algorithm which finds a stable matching in $O(n^2)$ communication rounds. Their algorithm has a natural interpretation as a distributed algorithm where each player is represented by a single processor. In this distributed model, Floreen, Kaski, Polishchuk, and Suomela recently showed that for bounded preference lists, terminating the Gale-Shapley algorithm after a constant number of rounds results in an almost stable matching. In this paper, we describe a new deterministic distributed algorithm which finds an almost stable matching in $O(lo{g}^{5}n)$ communication rounds for arbitrary preferences. We also present a faster randomized variant which requires $O(lo{g}^{2}n)$ rounds. This run-time can be improved to $O(1)$ rounds for "almost regular" (and in particular complete) preferences. To our knowledge, these are the first sub-polynomial round distributed algorithms for any variant of the stable marriage problem with unbounded preferences.

Recommendations

• Algorithms – ESA 2004
• Faster and simpler approximation of stable matchings
• Faster and simpler approximation of stable matchings
• Distributed near-optimal matching
• Distributed near-optimal matching
• Distributed Stable Matching Problems
• Distributed algorithm for approximating the maximum matching
• Dynamic and self-stabilizing distributed matching
• scientific article; zbMATH DE number 1003296
• A sublinear parallel algorithm for stable matching

Cites work

• scientific article; zbMATH DE number 826255 (Why is no real title available?)
• Memorization and Association on a Realistic Neural Model

Cited in

(13)

• Distributed near-optimal matching
• Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists
• Faster and simpler approximation of stable matchings
• Almost stable matchings by truncating the Gale-Shapley algorithm
• Stable secretaries
• A stable marriage requires communication
• Distributed stable matching with similar preference lists
• Distributed Stable Matching Problems
• Communication requirements for stable marriages
• Self-stabilizing distributed stable marriage
• Legal Assignments and Fast EADAM with Consent via Classic Theory of Stable Matchings
• Distributed near-optimal matching
• On the complexity of distributed stable matching with small messages

This page was built for publication: Fast distributed almost stable matchings

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2796247)