The complexity of approximately counting stable roommate assignments

DOI10.1016/j.jcss.2012.02.003zbMath1244.68038arXiv1012.1237OpenAlexW1623719451MaRDI 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 countingroommate assignment problem

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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