A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties

DOI10.4230/LIPIcs.APPROX-RANDOM.2015.361zbMath1375.68219OpenAlexW1930893454MaRDI QIDQ5351911

Chien-Chung Huang, Hiroki Yanagisawa, Shuichi Miyazaki, Kazuo Iwama

Publication date: 31 August 2017

Full work available at URL: https://dx.doi.org/10.4230/LIPIcs.APPROX-RANDOM.2015.361

zbMATH Keywords

approximation algorithminteger programintegrality gaplinear program relaxationstable marriage with ties and incomplete lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Matching models (91B68)

Related Items (3)

Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Tight inapproximability of minimum maximal matching on bipartite graphs and related problems

This page was built for publication: A Tight Approximation Bound for the Stable Marriage Problem with Restricted Ties