Linear time local approximation algorithm for maximum stable marriage
type: Item
instance of: scholarly article
title: Linear time local approximation algorithm for maximum stable marriage
zbMATH Open document ID: 1461.68257
author: Zoltán Király
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: We consider a two-sided market under incomplete preference lists with ties, where the goal is to find a maximum size stable matching. The problem is APX-hard, and a \(3/2\)-approximation was given by \textit{E. McDermid} [Lect. Notes Comput. Sci. 5555, 689--700 (2009; Zbl 1248.68564)]. This algorithm has a non-linear running time, and, more importantly needs global knowledge of all preference lists. We present a very natural, economically reasonable, local, linear time algorithm with the same ratio, using some ideas of \textit{K. Paluch} [Lect. Notes Comput. Sci. 7164, 176--187 (2012; Zbl 1242.68371)]. In this algorithm every person make decisions using only their own list, and some information asked from members of these lists (as in the case of the famous algorithm of Gale and Shapley). Some consequences to the Hospitals/Residents problem are also discussed.
Mathematics Subject Classification ID: 68W25
Mathematics Subject Classification ID: 91B26
Mathematics Subject Classification ID: 91B68
zbMATH DE Number: 7042173
zbMATH Keywords: stable marriage
zbMATH Keywords: Gale-Shapley algorithm
zbMATH Keywords: approximation
zbMATH Keywords: hospitals/residents problem
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6030471
OpenAlex ID: W2073547397
cites work: A 3/2-Approximation Algorithm for General Stable Marriage
cites work: Faster and Simpler Approximation of Stable Matchings
cites work: College Admissions and the Stability of Marriage
cites work: Better and Simpler Approximation Algorithms for the Stable Marriage Problem
cites work: Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
cites work: Improved approximation results for the stable marriage problem
cites work: Q2934607
cites work: Randomized approximation of the stable marriage problem
cites work: Q4938640
cites work: Hard variants of stable marriage.
cites work: Approximability results for stable marriage problems with ties.
cites work: Approximation Algorithms for the Sex-Equal Stable Marriage Problem
cites work: Better and simpler approximation algorithms for the stable marriage problem
cites work: Finding large stable matchings
cites work: A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
cites work: Storing a Sparse Table with 0 (1) Worst Case Access Time
cites work: Q3995616
DOI: 10.3390/A6030471
description: scientific article; zbMATH DE number 7042173