CODEWITHSUNDEEP
algorithmoptimizationgraphconstraints
Samuel
Samuel

Reputation: 686

Affect m students to n groups?

I'd like to affect m groups (m ~ 20) of students to n projects (n ~ 6). There is an additional constraint : I can only affect beetween p (p ~ 4) to q (q ~ 6) groups to each project.

Each group has to order the projects from the one it likes most to the worst.

I've read I could use the Hungarian algorithm if m = n and I should use the Ford-Fulkerson algorithm or the Edmonds–Karp algorithm in the general case.

Could you please help me to discern what will the graph be in my case ? I guess nodes are groups and projects, and edges have a cost determined by the way groups like projects. But what is the capacity property ? And how to respect my original constraint ?

Upvotes: 0

Views: 95

Answers (1)

kraskevich
kraskevich

Reputation: 18566

The graph should look this way:

  1. The source node.

  2. The sink node.

  3. The first set of nodes. These nodes correspond to groups of students(one node for each group). There should be an edge from the source node to each node from this set with capacity = 1(I assume that each group can do only project) and cost = 0.

  4. The second set of nodes. These nodes correspond to projects. There should be an edge from each node from this group to the sink node with cost = 0 and capacity = the maximum number of groups that are allowed to do this project.

  5. There should be an edge from each node from the first set to each node from the second set with capacity = 1 and cost = -how much this group likes this project(- is necessary if and only if the bigger this number is, the more this group likes this project).

  6. Now we have to find the minimum cost maximum flow from the source to the sink node.

Upvotes: 1

Related Questions