Popularity at minimum cost

DOI10.1007/s10878-012-9537-0zbMath1296.90105arXiv1009.2591WikidataQ62045773 ScholiaQ62045773MaRDI QIDQ2015798

Telikepalli Kavitha, Meghana Nasre, Prajakta Nimbhorkar

Publication date: 24 June 2014

Published in: Journal of Combinatorial Optimization, Algorithms and Computation (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1009.2591

zbMATH Keywords

bipartite graphs; matchings; NP-hardness; one-sided preference lists

Mathematics Subject Classification ID

90C27: Combinatorial optimization

90C39: Dynamic programming

05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)

Related Items

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

Cites Work

• Unnamed Item
• Popular mixed matchings
• Popular matchings with variable item copies
• Popular matchings: structure and algorithms
• Optimal popular matchings
• Popularity at minimum cost
• Rank-maximal matchings
• Popular Matchings
• 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