Popular matchings with variable item copies

DOI10.1016/J.TCS.2010.12.067MaRDI QIDQ631788zbMATH OpenOpenAlexWikidataFDO

Authors 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

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

Recommendations

• Popular matchings with variable job capacities
• Popular matchings
• Popular Matchings

Cites work

• Algorithms and Computation
• Bounded Unpopularity Matchings
• scientific article; zbMATH DE number 863471 (Why is no real title available?)
• Popular Matchings
• Popular Matchings in the Capacitated House Allocation Problem
• Popular matchings with variable job capacities
• Popular Mixed Matchings
• Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems
• Rank-maximal matchings
• The complexity of satisfiability problems
• The Least-Unpopularity-Factor and Least-Unpopularity-Margin Criteria for Matching Problems with One-Sided Preferences
• 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
• Weighted Popular Matchings

Cited in

(8)

• Popular matchings of desired size
• Minimal envy and popular matchings
• The generalized popular condensation problem
• Maintaining Near-Popular Matchings
• The popular matching and condensation problems under matroid constraints
• Popular matchings with variable job capacities
• Popular matchings with ties and matroid constraints
• Generalized capacity planning for the hospital-residents problem

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

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