what is the complexity and how to start

Question

Every year, Prof Gupta assigns the instructors to various faculty committees. There are n faculty members and c committees. Each committee member has submitted a list of their prices for serving on each committee; each price could be positive, negative, zero, or even infinite. For example, Professor Jindal might declare that he would serve on the Student Recruiting Committee for 1000 Rs, that he would pay 10000 Rs to serve on the Drug abuse Committee and that he would not serve on the Discipline committee for any price. Conversely, Gupta knows how many instructors are needed for each committee, as well as a list of instructors who would be suitable members for each committee. If Gupta assigns an instructor to a committee, he must pay that instructor’s price from the University treasury. Gupta needs to assign instructors to committees so that (1) each committee is full, (3) no instructor is assigned to more than three committees, (2) only suitable and willing instructors are assigned to each committee, and (4) the total cost of the assignment is as small as possible. Write an efficient algorithm that either solves Gupta’s problem, or correctly reports that there is no valid assignment whose total cost is finite.

Answer 1

These problem is a modification of the assigment problem, and can be solved by finding the minimum cost maximum flow in an appropriate graph.

You need to build the graph with:

• a sink node
• a source node
• a node for each commitee
• a node for each professor
• an edge between each commitee and each professor that can work on it with capacity $1$ and cost the ammount of money that the professor need
• an edge between the sink and each commitee with cost $0$ and flow the number of needed professors
• an edge between every professor and the source with cost $0$ and capacity $3$ (so any professor do not work in more than 3 committees)

And the find if is possible to send from sink to source the ammount of needed professors, and how much it cost.

Answer 2

I think it is a variant of http://en.wikipedia.org/wiki/Stable_marriage_problem

http://en.wikipedia.org/wiki/National_Resident_Matching_Program#Matching_algorithm

would be more suitable for your case, since more than one prof can be assigned to each committee.