How can I reduce my problem into Max flow problem?

by yns   Last Updated January 12, 2018 23:05 PM

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?

Tags : algorithms


Answers 2


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.

Ofir
Ofir
June 16, 2013 07:22 AM

What if we add an addition requirement: There are 5 periods, each student can only take one class per period classes are, instead of all day, in a certain period

Naixin Zong
Naixin Zong
January 12, 2018 22:27 PM

Related Questions


Calendar/Planning algorithm

Updated August 13, 2015 17:02 PM

Dynamic Scheduling Algorithm

Updated August 09, 2017 22:05 PM


Spreading objects in bags and bags' compartments

Updated March 06, 2017 02:05 AM

finding dog scheduler algorithm

Updated July 01, 2017 07:05 AM