Stable marriage with ties and bounded length preference lists

DOI10.1016/j.jda.2008.09.003zbMath1187.68346OpenAlexW1996180590MaRDI QIDQ1026229

Gregg O'Malley, David F. Manlove, Robert W. Irving

Publication date: 24 June 2009

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2008.09.003

zbMATH Keywords

tiespolynomial-time algorithmNP-hardnessstable marriage problemincomplete lists

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Strategyproof mechanism for two-sided matching with resource allocation ⋮ Hardness and approximation results for some variants of stable marriage problem ⋮ Optimal cost-based allocations under two-sided preferences ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ Two hardness results for core stability in hedonic coalition formation games ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ Mathematical models for stable matching problems with ties and incomplete lists ⋮ Strongly stable and maximum weakly stable noncrossing matchings ⋮ Stable fractional matchings ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ A 25/17-approximation algorithm for the stable marriage problem with one-sided ties ⋮ Keeping partners together: Algorithmic results for the hospitals/residents problem with couples ⋮ Improving solution times for stable matching problems through preprocessing ⋮ Balanced stable marriage: how close is close enough? ⋮ Maximum stable matching with one-sided ties of bounded length ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ The stable marriage problem with ties and restricted edges

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Some remarks on the stable matching problem
• Some simplified NP-complete graph problems
• Stable marriage and indifference
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Randomized approximation of the stable marriage problem
• The Complexity of Counting Stable Marriages
• Faster Scaling Algorithms for Network Problems
• Algorithm Theory - SWAT 2004
• Algorithms - ESA 2003
• Algorithms and Computation
• College Admissions and the Stability of Marriage

This page was built for publication: Stable marriage with ties and bounded length preference lists