NP-complete stable matching problems
From MaRDI portal
Publication:3485870
DOI10.1016/0196-6774(90)90007-2zbMath0705.68065OpenAlexW2000017271WikidataQ63443885 ScholiaQ63443885MaRDI QIDQ3485870
Publication date: 1990
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(90)90007-2
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
Splitting a configuration in a simplex ⋮ COALITION FORMATION GAMES: A SURVEY ⋮ Stable matching of student-groups to dormitories ⋮ Matching couples with Scarf's algorithm ⋮ Testing substitutability of weak preferences ⋮ The stable fixtures problem -- a many-to-many extension of stable roommates ⋮ Stable matchings of teachers to schools ⋮ Non-existence of stable social groups in information-driven networks ⋮ Integer programming methods for special college admissions problems ⋮ Paths to stability for matching markets with couples ⋮ Stability in Large Matching Markets with Complementarities ⋮ Review of the theory of stable matchings and contract systems ⋮ Balancing stability and efficiency in team formation as a generalized roommate problem ⋮ Perfect matching in bipartite hypergraphs subject to a demand graph ⋮ ``Almost-stable matchings in the hospitals/residents problem with couples ⋮ Finding all stable matchings with couples ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Parameterized algorithms for stable matching with ties and incomplete lists ⋮ Pareto optimality in coalition formation ⋮ Three-sided stable matchings with cyclic preferences ⋮ Housing markets through graphs ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ An algorithm for a super-stable roommates problem ⋮ Two hardness results for core stability in hedonic coalition formation games ⋮ Approximability results for stable marriage problems with ties. ⋮ Matching with sizes (or scheduling with processing set restrictions) ⋮ A General Framework for Stable Roommates Problems using Answer Set Programming ⋮ The stable roommates problem with short lists ⋮ How hard is it to satisfy (almost) all roommates ⋮ An unfeasible matching problem ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Overlays with preferences: distributed, adaptive approximation algorithms for matching with preference lists ⋮ Some things couples always wanted to know about stable matchings (but were afraid to ask) ⋮ Fractional solutions for capacitated NTU-games, with applications to stable matchings ⋮ Size versus stability in the marriage problem ⋮ Deferred acceptance algorithms: history, theory, practice, and open questions ⋮ Keeping partners together: Algorithmic results for the hospitals/residents problem with couples ⋮ Geometric stable roommates ⋮ Stability and Nash implementation in matching markets with couples ⋮ Stable matchings and preferences of couples ⋮ Size Versus Stability in the Marriage Problem ⋮ On the complexity of exchange-stable roommates ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ The Stable Roommates Problem with Short Lists ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ Stable partitions with \(\mathcal W\)-preferences ⋮ The stable crews problem ⋮ MATCHING WITH COUPLES: A MULTIDISCIPLINARY SURVEY ⋮ The exchange-stable marriage problem ⋮ Strategic Issues in One-to-One Matching with Externalities ⋮ Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters ⋮ Stable marriage and indifference ⋮ Hard variants of stable marriage. ⋮ The hospitals/residents problem with lower quotas
