Parameterized complexity and local search approaches for the stable marriage problem with ties
From MaRDI portal
Publication:1959726
DOI10.1007/s00453-009-9326-zzbMath1204.68148OpenAlexW2000321198MaRDI QIDQ1959726
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
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
