Almost stable matchings by truncating the Gale-Shapley algorithm
From MaRDI portal
Publication:1959728
DOI10.1007/s00453-009-9353-9zbMath1204.68144WikidataQ57540239 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
local algorithms; almost stable matching; constant-time randomised algorithms; distributed stable matching
68R05: Combinatorics in computer science
05A05: Permutations, words, matrices
68R10: Graph theory (including graph drawing) in computer science
Related Items
Weak models of distributed computing, with connections to modal logic, ``Almost stable matchings in the roommates problem with bounded preference lists, Local approximability of max-min and min-max linear programs, ``Almost-stable matchings in the hospitals/residents problem with couples, Local Matching Dynamics in Social Networks
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
