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

algorithmsmatchingvotingNP-hardnesspopular matchingone-sided preferences

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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

(30)

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

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)