An efficient algorithm for the “stable roommates” problem
From MaRDI portal
Publication:3703906
DOI10.1016/0196-6774(85)90033-1zbMath0581.05001OpenAlexW2068574579WikidataQ57311970 ScholiaQ57311970MaRDI QIDQ3703906
Publication date: 1985
Published in: Journal of Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0196-6774(85)90033-1
Permutations, words, matrices (05A05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete mathematics in relation to computer science (68R99)
Related Items (only showing first 100 items - show all)
Review of the theory of stable matchings and contract systems ⋮ On stable flows and preflows ⋮ Stable and meta-stable contract networks ⋮ Marriage and Roommate ⋮ Distance on matchings: An axiomatic approach ⋮ On the set of stable matchings in a bipartite graph ⋮ Balancing stability and efficiency in team formation as a generalized roommate problem ⋮ The dynamics of rank-maximal and popular matchings ⋮ Novel integer programming models for the stable kidney exchange problem ⋮ Stable matchings and linear inequalities ⋮ COALITION FORMATION GAMES: A SURVEY ⋮ NP-completeness in hedonic games ⋮ Stable Marriage and Roommates Problems with Restricted Edges: Complexity and Approximability ⋮ The cycle roommates problem: a hard case of kidney exchange ⋮ Testing substitutability of weak preferences ⋮ The stable fixtures problem -- a many-to-many extension of stable roommates ⋮ Stable matchings and stable partitions∗ ⋮ The core of housing markets from an agent's perspective: Is it worth sprucing up your home? ⋮ A Polyhedral Description of Kernels ⋮ The stable fixtures problem with payments ⋮ On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm ⋮ A local interaction dynamic for the matching problem ⋮ Popular matchings in complete graphs ⋮ Stable matching with network externalities ⋮ Analysis of stochastic matching markets ⋮ Stable matchings and linear programming ⋮ Essentially stable matchings ⋮ The three-dimensional stable roommates problem with additively separable preferences ⋮ Two problems in max-size popular matchings ⋮ Subquadratic algorithms for succinct stable matching ⋮ Robust and approximately stable marriages under partial information ⋮ The Stable Roommates Problem with Choice Functions ⋮ The core of roommate problems: size and rank-fairness within matched pairs ⋮ Finding kernels or solving SAT ⋮ On a lemma of Scarf. ⋮ ``Almost stable matchings in the roommates problem with bounded preference lists ⋮ Locally Stable Marriage with Strict Preferences ⋮ Unnamed Item ⋮ The complexity of approximately counting stable roommate assignments ⋮ Dynamics in matching and coalition formation games with structural constraints ⋮ The stable roommates problem with choice functions ⋮ Three-sided stable matchings with cyclic preferences ⋮ An efficient algorithm for batch stability testing ⋮ Faster algorithms for stable allocation problems ⋮ Stable assignment with couples: parameterized complexity and local search ⋮ An algorithm for a super-stable roommates problem ⋮ A maximum stable matching for the roommates problem ⋮ Two hardness results for core stability in hedonic coalition formation games ⋮ Subjective homophily and the fixtures problem ⋮ One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences ⋮ Bistable versions of the marriages and roommates problems ⋮ The stable tournament problem: matching sports schedules with preferences ⋮ 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 ⋮ A characterization of graphs that ensure the existence of stable matchings ⋮ The existence of a unique core partition in coalition formation games ⋮ The stable marriage problem: an interdisciplinary review from the physicist's perspective ⋮ Stable roommates problem with random preferences ⋮ Two-Sided Matching Models ⋮ Stable fractional matchings ⋮ matchingMarkets ⋮ Large roommate problem with non-transferable random utility ⋮ A bounded approximation for the minimum cost 2-sat problem ⋮ Stable marriage and roommates problems with restricted edges: complexity and approximability ⋮ On the stable \(b\)-matching problem in multigraphs ⋮ A new fixed point approach for stable networks and stable marriages ⋮ Efficient stabilization of cooperative matching games ⋮ Rotations in the stable \(b\)-matching problem ⋮ Size versus stability in the marriage problem ⋮ The dynamics of stable matchings and half-matchings for the stable marriage and roommates problems ⋮ Random paths to \(P\)-stability in the roommate problem ⋮ Deferred acceptance algorithms: history, theory, practice, and open questions ⋮ Geometric stable roommates ⋮ The roommate problem with externalities ⋮ Size Versus Stability in the Marriage Problem ⋮ Finding strongly popular \(b\)-matchings in bipartite graphs ⋮ On the complexity of exchange-stable roommates ⋮ Exchange-stability in roommate problems ⋮ Efficient algorithms for generalized stable marriage and roommates problems ⋮ Representing roommates' preferences with symmetric utilities ⋮ Refugee allocation in the setting of hedonic games ⋮ Hardness results for stable exchange problems ⋮ Unpopularity factor in the marriage and roommates problems ⋮ A generalization of the stable matching problem ⋮ Random stable matchings ⋮ Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties ⋮ The Stable Roommates Problem with Short Lists ⋮ Residence exchange wanted: A stable residence exchange problem ⋮ Pairwise Preferences in the Stable Marriage Problem ⋮ Coalitional permutation manipulations in the Gale-Shapley algorithm ⋮ Popular Matchings in Complete Graphs ⋮ Compact linear programs for 2SAT ⋮ The Stable Fixtures Problem with Payments ⋮ Stable matching with preferences derived from a psychological model ⋮ Borda-induced hedonic games with friends, enemies, and neutral players ⋮ Stable partitions with \(\mathcal W\)-preferences ⋮ The stable crews problem ⋮ On the convergence of swap dynamics to Pareto-optimal matchings ⋮ A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences
This page was built for publication: An efficient algorithm for the “stable roommates” problem
