The Complexity of Approximately Counting Stable Matchings

DOI10.1007/978-3-642-15369-3_7MaRDI QIDQ3588401zbMATH OpenOpenAlexFDO

Authors Prasad Chebolu, Leslie Ann Goldberg, Russell Martin

Publication date 10 September 2010

Published in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-15369-3_7

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Matching models (91B68)

Recommendations

• The complexity of approximately counting stable matchings
• Approximating stable matchings with ties of bounded size
• A simply exponential upper bound on the maximum number of stable matchings
• Faster and simpler approximation of stable matchings
• Faster and simpler approximation of stable matchings
• On the approximability of the stable matching problem with ties of size two
• The computational strength of matchings in countable graphs
• Algorithms and complexity of strongly stable non-crossing matchings
• An improved approximation lower bound for finding almost stable maximum matchings

Cited in

(7)

• The complexity of approximately counting stable roommate assignments
• The complexity of approximately counting stable matchings
• Center stable matchings and centers of cover graphs of distributive lattices
• The Complexity of Rationalizing Matchings
• A simply exponential upper bound on the maximum number of stable matchings
• The Complexity of Counting Stable Marriages
• Stable matchings in high dimensions via the Poisson-weighted infinite tree

This page was built for publication: The Complexity of Approximately Counting Stable Matchings

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