Popular matchings with variable item copies

DOI10.1016/j.tcs.2010.12.067zbMath1217.68161OpenAlexW2094637312WikidataQ62045779 ScholiaQ62045779MaRDI QIDQ631788

Telikepalli Kavitha, Meghana Nasre

Publication date: 14 March 2011

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

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

zbMATH Keywords

bipartite graphsmatchingsNP-hardnessone-sided preference lists

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) 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)

Related Items (5)

The popular matching and condensation problems under matroid constraints ⋮ The Generalized Popular Condensation Problem ⋮ Popular Matchings with Ties and Matroid Constraints ⋮ Minimal envy and popular matchings ⋮ Popularity at minimum cost

Cites Work

• Unnamed Item
• The stable marriage problem with master preference lists
• Using clausal graphs to determine the computational complexity of \(k\)-bounded positive one-in-three SAT
• Weak versus strong domination in a market with indivisible goods
• Rank-maximal matchings
• Bounded Unpopularity Matchings
• Popular Matchings
• Weighted Popular Matchings
• Popular Mixed Matchings
• Popular Matchings with Variable Job Capacities
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• The complexity of satisfiability problems
• Popular Matchings in the Capacitated House Allocation Problem
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• Algorithms and Computation

This page was built for publication: Popular matchings with variable item copies