Stable assignment with couples: parameterized complexity and local search
From MaRDI portal
Publication:456691
DOI10.1016/j.disopt.2010.07.004zbMath1248.90058OpenAlexW2037963188MaRDI QIDQ456691
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
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