An improved approximation lower bound for finding almost stable maximum matchings

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

zbMATH Keywords

approximation algorithmsapproximation ratiopolynomial-time reductionthe stable marriage problem

Mathematics Subject Classification ID

Approximation algorithms (68W25)

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

• Unnamed Item
• Some remarks on the stable matching problem
• Instability of matchings in decentralized markets with various preference structures
• Size Versus Stability in the Marriage Problem
• Approximation and Online Algorithms
• College Admissions and the Stability of Marriage

This page was built for publication: An improved approximation lower bound for finding almost stable maximum matchings