An efficient algorithm for the “stable roommates” problem

DOI10.1016/0196-6774(85)90033-1MaRDI QIDQ3703906zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Robert W. Irving

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

zbMATH Keywords

stable marriage problemstable matchingstable roommates problem

Mathematics Subject Classification ID

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)

Recommendations

• An algorithm for a super-stable roommates problem
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Efficient algorithms for generalized stable marriage and roommates problems
• A maximum stable matching for the roommates problem
• Approximation and Online Algorithms
• On a generalization of the stable roommates problem
• The complexity of approximately counting stable roommate assignments
• The ``stable roommates problem with random preferences
• On the existence of stable roommate matchings

Cited in

(only showing first 100 items - show all)

• Efficient algorithms and methods to solve dynamic MINs stability problem using stable matching with complete ties
• Worst-case choice for the stable marriage problem
• The average performance of a parallel stable mariage algorithm
• A characterization of graphs that ensure the existence of stable matchings
• A bounded approximation for the minimum cost 2-sat problem
• A new fixed point approach for stable networks and stable marriages
• Residence exchange wanted: A stable residence exchange problem
• Stable marriage and indifference
• Stable matchings and linear inequalities
• On a lemma of Scarf.
• A sublinear parallel algorithm for stable matching
• On a cutting plane heuristic for the stable roommates problem and its applications
• A polynomial-time algorithm for the bistable roommates problem
• Hard variants of stable marriage.
• The stable fixtures problem with payments
• Dynamics in matching and coalition formation games with structural constraints
• The stable tournament problem: matching sports schedules with preferences
• The stable roommates problem with short lists
• The existence of a unique core partition in coalition formation games
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• A generalization of the stable matching problem
• Stable matching with preferences derived from a psychological model
• On the decomposability of the stable marriage problem
• Stable partitions with \(\mathcal W\)-preferences
• The stable crews problem
• NP-completeness in hedonic games
• Stable matchings and linear programming
• The roommates problem revisited
• The stable roommates problem with choice functions
• Three-sided stable matchings with cyclic preferences
• An efficient algorithm for batch stability testing
• A polynomial-time algorithm to find von Neumann-Morgenstern stable matchings in marriage games
• Faster algorithms for stable allocation problems
• Bistable versions of the marriages and roommates problems
• The roommate problem with externalities
• Unpopularity factor in the marriage and roommates problems
• Coalitional permutation manipulations in the Gale-Shapley algorithm
• A collection of constraint programming models for the three-dimensional stable matching problem with cyclic preferences
• Parameterized complexity of stable roommates with ties and incomplete lists through the lens of graph parameters
• Stable matching of student-groups to dormitories
• The core of housing markets from an agent's perspective: Is it worth sprucing up your home?
• A local interaction dynamic for the matching problem
• Essentially stable matchings
• Robust and approximately stable marriages under partial information
• Subjective homophily and the fixtures problem
• One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
• The stable marriage problem: an interdisciplinary review from the physicist's perspective
• Stable fractional matchings
• Exchange-stability in roommate problems
• Refugee allocation in the setting of hedonic games
• Stable noncrossing matchings
• Compact linear programs for 2SAT
• Borda-induced hedonic games with friends, enemies, and neutral players
• The cycle roommates problem: a hard case of kidney exchange
• The stable fixtures problem -- a many-to-many extension of stable roommates
• Stable matching with network externalities
• Two problems in max-size popular matchings
• The core of roommate problems: size and rank-fairness within matched pairs
• Two hardness results for core stability in hedonic coalition formation games
• On the stable \(b\)-matching problem in multigraphs
• A unified and efficient solution to the room search 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
• The exchange-stable marriage problem
• Testing substitutability of weak preferences
• Popular matchings in complete graphs
• The three-dimensional stable roommates problem with additively separable preferences
• Stable marriages with restricted pairs
• The Stable Roommates Problem with Short Lists
• The stable fixtures problem with payments
• Best optimal stable matching
• scientific article; zbMATH DE number 4133845 (Why is no real title available?)
• scientific article; zbMATH DE number 1003296 (Why is no real title available?)
• A Polyhedral Description of Kernels
• A necessary and sufficient condition for the existence of a complete stable matching
• Stable roommates problem with random preferences
• A Note on the Room-Mates Problem and a Related Revenue Allocation Problem
• COALITION FORMATION GAMES: A SURVEY
• Stable marriage and roommates problems with restricted edges: complexity and approximability
• Lower Bounds for the Stable Marriage Problem and Its Variants
• The Stable Roommates Problem with Choice Functions
• The Stable Roommates Problem with Globally Ranked Pairs
• Size Versus Stability in the Marriage Problem
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• Analysis of stochastic matching markets
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• On a new algorithm for stable assignment^*
• Stable matchings and stable partitions^∗
• scientific article; zbMATH DE number 45086 (Why is no real title available?)
• Finding kernels or solving SAT
• ``Almost stable matchings in the roommates problem with bounded preference lists
• On a Random Instance of a ‘Stable Roommates’ Problem: Likely Behavior of the Proposal Algorithm
• A New Approach to Stable Matching Problems
• The complexity of approximately counting stable roommate assignments
• scientific article; zbMATH DE number 2038736 (Why is no real title available?)
• Stable assignment with couples: parameterized complexity and local search
• scientific article; zbMATH DE number 1369412 (Why is no real title available?)
• The kissing problem: how to end a gathering when everyone kisses everyone else goodbye

This page was built for publication: An efficient algorithm for the “stable roommates” problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3703906)