Popular matching in roommates setting is \textsf{NP}-hard

MaRDI QIDQ5011876zbMATH OpenFDO

Authors Sushmita Gupta, Pranabendu Misra, Saket Saurabh, Meirav Zehavi

Publication date 30 August 2021

Full work available at URL http://bulletin.eatcs.org/index.php/beatcs/article/view/613/621

Mathematics Subject Classification ID

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) Matching models (91B68)

Recommendations

• Popular matchings in the marriage and roommates problems
• Near-popular matchings in the roommates problem
• Near-popular matchings in the roommates problem

Cited in

(6)

• Near-popular matchings in the roommates problem
• Popular matchings in the marriage and roommates problems
• Near-popular matchings in the roommates problem
• Popular Roommates in Simply Exponential Time.
• Popularity on the roommate diversity problem
• Popularity on the roommate diversity problem

This page was built for publication: Popular matching in roommates setting is \textsf{NP}-hard

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