Popularity at minimum cost

DOI10.1007/s10878-012-9537-0zbMath1296.90105arXiv1009.2591OpenAlexW1630623148WikidataQ62045773 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 graphsmatchingsNP-hardnessone-sided preference lists

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Dynamic programming (90C39) 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)

Related Items (5)

The popular matching and condensation problems under matroid constraints ⋮ The Generalized Popular Condensation Problem ⋮ Hedonic diversity games: a complexity picture with more than two colors ⋮ Popular Matchings with Ties and Matroid Constraints ⋮ Popularity at minimum cost

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

This page was built for publication: Popularity at minimum cost