0

I am trying to reduce my problem to a max flow problem so I can run the max flow algorithm on this problem. But there are some things that I am missing while transforming my problem.

My problem is:

  • there are classes with a maximum capacity
  • there are students and their wish-list that includes 5 classes that they want
  • students can select at most 5 classes.

And the goal is:

  • to maximize number of classes that students enroll.

Image

If I put students and classes as vertices (please see image above), then put a source node s that has an edge to each student and a sink node t that has an edge to each classes, what will be the edge costs?

  • edge cost between classes and sink node t or
  • edge cost between source node s and and students

Are the following assumptions correct?
I think the edge between students and classes cost should be 1. Because a student can only enroll once to a class in a term. I think edge cost between classes and the sink node t will be the maximum capacity of a class.

I don't have an idea about edge costs between source node s and students nodes.

And at the end, after arranging, do we just need to run max flow algorithm?

1

I think that a max flow from S to any student of 5, and max flow of capacity from each class to T and 1 from each student to each class would satisfy your requirements. BTW, that is not an edge cost but rather an edge flow capacity.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.