The complexity of approximately counting stable roommate assignments

DOI10.1016/j.jcss.2012.02.003zbMath1244.68038arXiv1012.1237MaRDI QIDQ440007

Leslie Ann Goldberg, Russell Martin, Prasad Chebolu

Publication date: 17 August 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1012.1237

zbMATH Keywords

approximate counting; roommate assignment problem

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68R05: Combinatorics in computer science

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

Stable marriage with groups of similar agents, Solving hard stable matching problems involving groups of similar agents, A number of stable matchings in models of the Gale-Shapley type

Cites Work

• Unnamed Item
• Unnamed Item
• Random generation of combinatorial structures from a uniform distribution
• The relative complexity of approximate counting problems
• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• The Complexity of Ferromagnetic Ising with Local Fields
• The Complexity of Approximately Counting Stable Matchings
• An efficient algorithm for the “stable roommates” problem
• The Complexity of Counting Stable Marriages
• The Structure of the Stable Roommate Problem: Efficient Representation and Enumeration of All Stable Assignments
• Linear Datalog and Bounded Path Duality of Relational Structures
• On Unapproximable Versions of $NP$-Complete Problems
• College Admissions and the Stability of Marriage