Linear time local approximation algorithm for maximum stable marriage
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.
- Better and simpler approximation algorithms for the stable marriage problem
- Better and Simpler Approximation Algorithms for the Stable Marriage Problem
- A 3/2-Approximation Algorithm for General Stable Marriage
- Faster and simpler approximation of stable matchings
- Improved approximation of the stable marriage problem
- A 25/17-approximation algorithm for the stable marriage problem with one-sided ties
- A 3/2-Approximation Algorithm for General Stable Marriage
- A 1.875-approximation algorithm for the stable marriage problem
- Approximability results for stable marriage problems with ties.
- Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
- Approximation Algorithms for the Sex-Equal Stable Marriage Problem
- Better and simpler approximation algorithms for the stable marriage problem
- Better and Simpler Approximation Algorithms for the Stable Marriage Problem
- College Admissions and the Stability of Marriage
- Faster and simpler approximation of stable matchings
- Finding large stable matchings
- Hard variants of stable marriage.
- scientific article; zbMATH DE number 45086 (Why is no real title available?)
- scientific article; zbMATH DE number 1405659 (Why is no real title available?)
- Improved approximation results for the stable marriage problem
- Linear time local approximation algorithm for maximum stable marriage
- Randomized approximation of the stable marriage problem
- Storing a Sparse Table with 0 (1) Worst Case Access Time
- Maximum locally stable matchings
- Linear time local approximation algorithm for maximum stable marriage
- Local search approaches in stable matching problems
- Editorial: Special issue on matching under preferences
- Mathematical models for stable matching problems with ties and incomplete lists
- Matching with indifferences: a comparison of algorithms in the context of course allocation
- Almost stable matchings by truncating the Gale-Shapley algorithm
- On the approximability of the stable matching problem with ties of size two
- On treewidth and stable marriage: parameterized algorithms and hardness results (complete characterization)
- A 3 / 2 -approximation Algorithm for the Student-Project Allocation Problem
- Maximum stable matching with one-sided ties of bounded length
- Hardness and approximation results for some variants of stable marriage problem
- Incomplete list setting of the hospitals/residents problem with maximally satisfying lower quotas
- Critical Relaxed Stable Matchings with Two-Sided Ties
- A new heuristic algorithm for student-project allocation with lecturer preferences and ties
- Hardness and approximation results for some variants of stable marriage problem
- Characterization of super-stable matchings
- Improved approximation algorithms for two variants of the stable marriage problem with ties
This page was built for publication: Linear time local approximation algorithm for maximum stable marriage
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1736578)
