The complexity of approximately counting stable matchings

DOI10.1016/j.tcs.2012.02.029zbMath1310.68103OpenAlexW2055193025MaRDI QIDQ441846

Leslie Ann Goldberg, Russell Martin, Prasad Chebolu

Publication date: 8 August 2012

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2012.02.029

zbMATH Keywords

stable marriage problemapproximation-preserving reductioncounting independent sets in bipartite graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Matching models (91B68)

Related Items (4)

Counting vertices of integral polytopes defined by facets ⋮ Stable marriage with groups of similar agents ⋮ Solving hard stable matching problems involving groups of similar agents ⋮ Algorithms for #BIS-Hard Problems on Expander Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A counterexample to rapid mixing of the Ge-Stefankovic process
• Euclidean preferences
• 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
• Approximating the Partition Function of the Ferromagnetic Potts Model
• The Complexity of Counting Stable Marriages
• Three Fast Algorithms for Four Problems in Stable Marriage
• Linear Datalog and Bounded Path Duality of Relational Structures
• College Admissions and the Stability of Marriage

This page was built for publication: The complexity of approximately counting stable matchings