Almost stable matchings by truncating the Gale-Shapley algorithm

DOI10.1007/s00453-009-9353-9zbMath1204.68144OpenAlexW2004854811WikidataQ57540239 ScholiaQ57540239MaRDI QIDQ1959728

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

Publication date: 7 October 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9353-9

zbMATH Keywords

local algorithmsalmost stable matchingconstant-time randomised algorithmsdistributed stable matching

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (5)

``Almost-stable matchings in the hospitals/residents problem with couples ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Local Matching Dynamics in Social Networks ⋮ Local approximability of max-min and min-max linear programs ⋮ Weak models of distributed computing, with connections to modal logic

Cites Work

• Unnamed Item
• Unnamed Item
• Analysing local algorithms in location-aware quasi-unit-disk graphs
• A parallel algorithm to solve the stable marriage problem
• Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
• The average performance of a parallel stable mariage algorithm
• On-line algorithms for weighted bipartite matching and stable marriages
• A sublinear parallel algorithm for stable matching
• Instability of matchings in decentralized markets with various preference structures
• Survey of local algorithms
• A survey of heuristics for the weighted matching problem
• Random Paths to Stability in Two-Sided Matching
• Fast Distributed Approximations in Planar Graphs
• The price of being near-sighted
• Size Versus Stability in the Marriage Problem
• Efficient Distributed Weighted Matchings on Trees
• Locality in Distributed Graph Algorithms
• What Can be Computed Locally?
• High Performance Computing - HiPC 2003
• Distributed Weighted Matching
• A Fixed-Point Approach to Stable Matchings and Some Applications
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: Almost stable matchings by truncating the Gale-Shapley algorithm