Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective

DOI10.1016/j.dam.2023.05.011zbMath1518.91172arXiv2106.09917OpenAlexW3175080860MaRDI QIDQ6162047

Girija Limaye

Publication date: 15 June 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2106.09917

zbMATH Keywords

fixed-parameter tractabilityparameterized complexitykernelizationenvy-freenessrelaxed stabilitylower-quotamatchings under two-sided preferences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Resource and cost allocation (including fair division, apportionment, etc.) (91B32) Matching models (91B68)

Cites Work

• The hospitals/residents problem with lower quotas
• Stable assignment with couples: parameterized complexity and local search
• The college admissions problem with lower and common quotas
• Parameterized algorithms for stable matching with ties and incomplete lists
• The lattice of envy-free matchings
• Parameterized complexity and local search approaches for the stable marriage problem with ties
• Envy-free matchings with lower quotas
• Stable matchings with covering constraints: a complete computational trichotomy
• A fine-grained view on stable many-to-one matching problems with lower and upper quotas
• Improved Distributed Approximate Matching
• How hard is it to satisfy (almost) all roommates
• Popular Matchings with Lower Quotas
• How Good Are Popular Matchings
• College Admissions and the Stability of Marriage
• Envy-freeness and relaxed stability: hardness and approximation algorithms
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective