Computer Science – Data Structures and Algorithms
Scientific paper
2010-12-29
Computer Science
Data Structures and Algorithms
Scientific paper
Suppose that each member of a set of agents has a preference list of a subset of houses, possibly involving ties and each agent and house has their capacity denoting the maximum number of correspondingly agents/houses that can be matched to him/her/it. We want to find a matching $M$, for which there is no other matching $M'$ such that more agents prefer $M'$ to $M$ than $M$ to $M'$. (What it means that an agent prefers one matching to the other is explained in the paper.) Popular matchings have been studied quite extensively, especially in the one-to-one setting. We provide a characterization of popular b-matchings for two defintions of popularity, show some $NP$-hardness results and for certain versions describe polynomial algorithms.
No associations
LandOfFree
Popular b-matchings does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Popular b-matchings, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Popular b-matchings will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-400179