An improved approximation lower bound for finding almost stable maximum matchings
From MaRDI portal
Publication:989570
DOI10.1016/j.ipl.2009.06.008zbMath1202.68484OpenAlexW2043144984MaRDI QIDQ989570
Kazuo Iwama, Koki Hamada, Shuichi Miyazaki
Publication date: 20 August 2010
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2433/226944
Related Items (12)
Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ Computing relaxations for the three-dimensional stable matching problem with cyclic preferences ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ Size versus stability in the marriage problem ⋮ The Stable Roommates Problem with Short Lists ⋮ (Un)stable matchings with blocking costs ⋮ The hospitals/residents problem with lower quotas
Cites Work
This page was built for publication: An improved approximation lower bound for finding almost stable maximum matchings