Parameterized complexity and local search approaches for the stable marriage problem with ties

DOI10.1007/s00453-009-9326-zzbMath1204.68148OpenAlexW2000321198MaRDI QIDQ1959726

Dániel Marx, Ildikó Schlotter

Publication date: 7 October 2010

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-009-9326-z

zbMATH Keywords

local searchparameterized complexitystable marriage with ties

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Permutations, words, matrices (05A05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (19)

Backdoors to Satisfaction ⋮ On Treewidth and Stable Marriage: Parameterized Algorithms and Hardness Results (Complete Characterization) ⋮ Stable marriage with groups of similar agents ⋮ Algorithms and complexity of strongly stable non-crossing matchings ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ The parameterized complexity of \(k\)-flip local search for SAT and MAX SAT ⋮ Parameterized dynamic cluster editing ⋮ Searching for better fill-in ⋮ How hard is it to satisfy (almost) all roommates ⋮ Local search approaches in stable matching problems ⋮ Sex-equal stable matchings: complexity and exact algorithms ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ 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 ⋮ Parameterized Dynamic Cluster Editing ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Stable assignment with couples: parameterized complexity and local search
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• Approximation algorithms for hard variants of the stable marriage and hospitals/residents problems
• Stable marriage and indifference
• Approximability results for stable marriage problems with ties.
• Hard variants of stable marriage.
• Every finite distributive lattice is a set of stable matchings for a small stable marriage instance
• On the Hardness of Losing Weight
• Better and Simpler Approximation Algorithms for the Stable Marriage Problem
• Three Fast Algorithms for Four Problems in Stable Marriage
• On Local Search and Placement of Meters in Networks
• College Admissions and the Stability of Marriage

This page was built for publication: Parameterized complexity and local search approaches for the stable marriage problem with ties