Allocating preferences

tags:

algorithm

views:

answers:

+1 Q:

Allocating preferences

If n beds are to be allocated to m people.Each may have multiple preferences or not prefer at all. How to satisfy maximum people. A person who had a preference and got the same will be accounted as a satisfied person.

I tried allocating a person with minimum preferences first with minimum preferred bed. Is there some case I am missing, because it gave me a wrong answer?

+4 A:

This is the maximum bipartite matching problem. Wiki has good algorithms, also look up maximum flow.

IVlad 2010-10-03 17:43:43

Can you please elaborate?

san8055 2010-10-03 17:51:12

@san8055 - it's pretty hard to elaborate, as this requires quite a bit of knowledge of graph algorithms? Specifically, you need to know what a graph is and what a BF search is. If you know these, then build a bipartite graph whose two sets are the `n` beds and the `m` people. You have an edge from a person to a bed if that person prefers that bed. Add capacity 1 to these edges. Then add a capacity 1 edge from a dummy node to each person, and then from each bed to another dummy node. Run a maximum flow algorithm from the first dummy node. The satured edges will represent your allocation.

IVlad 2010-10-03 17:58:20

@IVlad thanks a lot. Can u please say if anything is wrong in my assumption allocating a person with minimum preferences first with minimum preferred bed

san8055 2010-10-03 18:58:17

@san8055 - yes I can. Consider `p1` prefers `b1`, `p2` prefers `b2` and `b3` and `p3` prefers `b1` and `b3`. you might allocate `p1-b1`, `p2-b3`, then then `p3` will be blocked. If you allocate `p2-b2` then this won't happen, but how do you know to do this?

IVlad 2010-10-03 19:03:50

@IVlad after allocatin p1-b1 p3 can only have b3. But p2 can have b3 and b2. so i will prefer allocating p3-b3

san8055 2010-10-03 19:13:14

@san8055 - okay, how about `p1 - b1, b2`; `p2 - b1, b2`; `p3 - b2, b3`. How do you know who to start with? Let's say you start with `p3` and allocate `p3-b2`. Then you will be forced to allocate `p2-b1`, thus blocking `p1` from being allocated. You can allocate all 3 however if at first you allocate `p3-b3`.

IVlad 2010-10-03 19:23:04

thanks! got it :)

san8055 2010-10-03 19:26:10

ansaurus

tags:

views:

answers:

Allocating preferences

related questions