The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences

DOI10.1007/978-3-540-78773-0_51MaRDI QIDQ5458562zbMATH OpenOpenAlexFDO

Authors Richard Matthew McCutchen

Publication date 15 April 2008

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-540-78773-0_51

zbMATH Keywords

algorithmsmatchingNP-hardnessone-sided preferencespopular matchingvoting

Mathematics Subject Classification ID

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

Recommendations

• Bounded unpopularity matchings
• Bounded Unpopularity Matchings
• Unpopularity factor in the marriage and roommates problems
• Near-popular matchings in the roommates problem
• Near-popular matchings in the roommates problem

Cited in

(34)

• Maximum locally stable matchings
• Unpopularity factor in the marriage and roommates problems
• A pessimist's approach to one-sided matching
• Popular branchings and their dual certificates
• Minimal envy and popular matchings
• Popular and clan-popular b-matchings
• Popular ranking
• The generalized popular condensation problem
• Popular matchings in the stable marriage problem
• Social welfare in one-sided matching markets without money
• Popular matchings with two-sided preferences and one-sided ties
• Maintaining Near-Popular Matchings
• Bounded Unpopularity Matchings
• Popular branchings and their dual certificates
• Quasi-popular matchings, optimality, and extended formulations
• Finding and Recognizing Popular Coalition Structures
• Random popular matchings with incomplete preference lists
• Popular Matchings: Structure and Algorithms
• Popular matchings with two-sided preferences and one-sided ties
• Popular mixed matchings
• Popularity vs maximum cardinality in the stable marriage setting
• The dynamics of rank-maximal and popular matchings
• Popular matchings with variable item copies
• Bounded unpopularity matchings
• Maximum matchings and popularity
• Popular matchings with weighted voters
• Popular matchings: structure and algorithms
• Computational complexity of \(k\)-stable matchings
• Stable matchings, one-sided ties, and approximate popularity
• Improved approximation for unpopularity in (3, 3)-hypergraph matching with one-sided preferences
• Popular arborescences and their matroid generalization
• Matchings, relaxed popularity, and optimality
• Maximum matchings and popularity
• Popular matchings in the weighted capacitated house allocation problem

This page was built for publication: The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences

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