Please use this identifier to cite or link to this item: https://doi.org/10.15480/882.2637
Publisher DOI: 10.1007/s00453-019-00636-y
Title: Stable matchings with covering constraints: a complete computational trichotomy
Language: English
Authors: Mnich, Matthias  
Schlotter, Ildikó 
Keywords: Stable marriage;Lower quotas;Fixed-parameter algorithms
Issue Date: 6-Feb-2020
Publisher: Springer
Source: Algorithmica (2020)
Journal or Series Name: Algorithmica 
Abstract (english): Stable matching problems with lower quotas are fundamental in academic hiring andensuring operability of rural hospitals. Only few tractable (polynomial-time solvable)cases of stable matching with lower quotas have been identified; most such problemsareNP-hard and also hard to approximate (Hamada et al. in Algorithmica 74(1):440–465, 2016). We therefore consider stable matching problems with lower quotas under arelaxed notion of tractability, namely fixed-parameter tractability. By cloning hospitalswe focus on the case when all hospitals have upper quota equal to 1, which general-izes the setting of “arranged marriages” first considered by Knuth (Mariages stableset leurs relations avec d’autres problèmes combinatoires, Les Presses de l’Universitéde Montréal, Montreal, 1976). We investigate how a set of natural parameters, namelythe maximum length of preference lists for men and women, the number of distin-guished men and women, and the number of blocking pairs allowed determine thecomputational tractability of this problem. Our main result is a complete complexitytrichotomy: for each choice of parameters we either provide a polynomial-time algo-rithm, or anNP-hardness proof and fixed-parameter algorithm, orNP-hardness proofandW[1]-hardness proof. As corollary, we negatively answer a question by Hamadaet al. (Algorithmica 74(1):440–465, 2016) by showing fixed-parameter intractabil-ity parameterized by optimal solution size. We also classify all cases of one-sidedconstraints where only women may be distinguished.
URI: http://hdl.handle.net/11420/4786
DOI: 10.15480/882.2637
ISSN: 1432-0541
Institute: Algorithmen und Komplexität E-11 
Type: (wissenschaftlicher) Artikel
Appears in Collections:Publications with fulltext

Files in This Item:
File Description SizeFormat
Mnich-Schlotter2020_Article_StableMatchingsWithCoveringCon.pdfVerlags-PDF954,56 kBAdobe PDFThumbnail
View/Open
Show full item record

Page view(s)

50
Last Week
9
Last month
checked on Feb 23, 2020

Download(s)

9
checked on Feb 23, 2020

Google ScholarTM

Check

Export

This item is licensed under a Creative Commons License Creative Commons