Local search approaches in stable matching problems
type: Item
instance of: scholarly article
title: Local search approaches in stable matching problems
zbMATH Open document ID: 1461.05163
author: Mirco Gelain
author: Maria Silvia Pini
author: Francesca Rossi
author: Toby Walsh
author: Kristen Brent Venable
published in: Algorithms
publication date: 2019-03-26T00:00:00Z
review text: Summary: The stable marriage (SM) problem has a wide variety of practical applications, ranging from matching resident doctors to hospitals, to matching students to schools or, more generally, to any two-sided market. In the classical formulation, \(n\) men and \(n\) women express their preferences (via a strict total order) over the members of the other sex. Solving an SM problem means finding a stable marriage where stability is an envy-free notion: no man and woman who are not married to each other would both prefer each other to their partners or to being single. We consider both the classical stable marriage problem and one of its useful variations (denoted SMTI (Stable Marriage with Ties and Incomplete lists)) where the men and women express their preferences in the form of an incomplete preference list with ties over a subset of the members of the other sex. Matchings are permitted only with people who appear in these preference lists, and we try to find a stable matching that marries as many people as possible. Whilst the SM problem is polynomial to solve, the SMTI problem is NP-hard. We propose to tackle both problems via a local search approach, which exploits properties of the problems to reduce the size of the neighborhood and to make local moves efficiently. We empirically evaluate our algorithm for SM problems by measuring its runtime behavior and its ability to sample the lattice of all possible stable marriages. We evaluate our algorithm for SMTI problems in terms of both its runtime behavior and its ability to find a maximum cardinality stable marriage. Experimental results suggest that for SM problems, the number of steps of our algorithm grows only as \(O(n \log(n))\), and that it samples very well the set of all stable marriages. It is thus a fair and efficient approach to generate stable marriages. Furthermore, our approach for SMTI problems is able to solve large problems, quickly returning stable matchings of large and often optimal size, desp…
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 91B68
zbMATH DE Number: 7042180
zbMATH Keywords: local search
zbMATH Keywords: stable matching
zbMATH Keywords: sampling
zbMATH Keywords: ties and incomplete preference lists
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.3390/a6040591
OpenAlex ID: W2047128428
cites work: Q3995616
cites work: College Admissions and the Stability of Marriage
cites work: Hard variants of stable marriage.
cites work: Q4130997
cites work: Three Fast Algorithms for Four Problems in Stable Marriage
cites work: Random Paths to Stability in Two-Sided Matching
cites work: Approximability results for stable marriage problems with ties.
cites work: Randomized Approximation of the Stable Marriage Problem
cites work: Improved approximation results for the stable marriage problem
cites work: Algorithm Theory - SWAT 2004
cites work: A 25/17-Approximation Algorithm for the Stable Marriage Problem with One-Sided Ties
cites work: Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
cites work: Q2934607
cites work: Better and simpler approximation algorithms for the stable marriage problem
cites work: A 3/2-Approximation Algorithm for General Stable Marriage
cites work: Algorithmics of Matching Under Preferences
cites work: Parameterized complexity and local search approaches for the stable marriage problem with ties
cites work: Stable assignment with couples: parameterized complexity and local search
cites work: Finding large stable matchings
cites work: Size versus stability in the marriage problem
cites work: Stability, optimality and manipulation in matching problems with weighted preferences
cites work: Q3579506
cites work: Q4938640
cites work: Understanding the generalized median stable matchings
DOI: 10.3390/A6040591
description: scientific article; zbMATH DE number 7042180