Stable assignment with couples: parameterized complexity and local search

DOI10.1016/j.disopt.2010.07.004zbMath1248.90058OpenAlexW2037963188MaRDI QIDQ456691

Dániel Marx, Ildikó Schlotter

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.07.004

zbMATH Keywords

local searchstable matchingparameterized complexitycouplesscheduling with job restrictions

Mathematics Subject Classification ID

Abstract computational complexity for mathematical programming problems (90C60) Discrete location and assignment (90B80)

Related Items (21)

Matching couples with Scarf's algorithm ⋮ Backdoors to Satisfaction ⋮ The parameterized complexity of local search for TSP, more refined ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ Scheduling and fixed-parameter tractability ⋮ Envy-freeness and relaxed stability for lower-quotas: a parameterized perspective ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ Local search for string problems: brute-force is essentially optimal ⋮ Parameterized complexity and local search approaches for the stable marriage problem with ties ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ 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 ⋮ On the parameterized complexity of consensus clustering ⋮ Parameterized complexity of machine scheduling: 15 open problems ⋮ Stable matching games: manipulation via subgraph isomorphism ⋮ Balanced stable marriage: how close is close enough? ⋮ Stable matchings with covering constraints: a complete computational trichotomy ⋮ MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY ⋮ 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
• On miniaturized problems in parameterized complexity theory
• Searching the \(k\)-change neighborhood for TSP is W[1-hard]
• Keeping partners together: Algorithmic results for the hospitals/residents problem with couples
• A parameterized view on matroid optimization problems
• Some remarks on the stable matching problem
• Stability of matchings when individuals have preferences over colleagues
• Hard variants of stable marriage.
• Stable matchings and preferences of couples
• The Stable Roommates Problem with Ties
• NP-complete stable matching problems
• On the Hardness of Losing Weight
• An efficient algorithm for the “stable roommates” problem
• The Lattice Structure of the Set of Stable Matchings with Multiple Partners
• Color-coding
• Parallel machine scheduling with job assignment restrictions
• Matching with sizes (or scheduling with processing set restrictions)
• College Admissions and the Stability of Marriage

This page was built for publication: Stable assignment with couples: parameterized complexity and local search