I have been assigned to solve a modified problem of the classic Project Allocation. It is half programming, but I've seen people post graph theory problems here, so I decided to try, since i couldn't find a way to even starts the assignment on my own.
We have x Contestants(C1,C2,...,Cx) and y Judges(G={J1,J2,...,Jy}). Groups of n Judges have to evaluate the Contestants' projects.
A Judge is either allowed or not to participate in the evaluation of a certain project.
Each Judge, Jk, can be in at most pk evaluating groups. The group of judges that can evaluate the project of contestant Cj is Gj\(\displaystyle \subsetneq\) G \(\displaystyle (G_{J} \neq \varnothing) . \)
Each project is evaluated by a group of n\(\displaystyle (\le y)\) Judges, m(\(\displaystyle \le n) \) being allowed to evaluate said project, and (n-m) not being able to.
(i) Make a NetFlow Model for which Judge will evaluate which project.
(ii) Sketch an algorithm (pseudocode) to check if a solution exists using maximum flows. Prove that it works and give an example on the model from (i).
(iii) What would be the time complexity for the algorithm that checks the existence of a solution?
We have x Contestants(C1,C2,...,Cx) and y Judges(G={J1,J2,...,Jy}). Groups of n Judges have to evaluate the Contestants' projects.
A Judge is either allowed or not to participate in the evaluation of a certain project.
Each Judge, Jk, can be in at most pk evaluating groups. The group of judges that can evaluate the project of contestant Cj is Gj\(\displaystyle \subsetneq\) G \(\displaystyle (G_{J} \neq \varnothing) . \)
Each project is evaluated by a group of n\(\displaystyle (\le y)\) Judges, m(\(\displaystyle \le n) \) being allowed to evaluate said project, and (n-m) not being able to.
(i) Make a NetFlow Model for which Judge will evaluate which project.
(ii) Sketch an algorithm (pseudocode) to check if a solution exists using maximum flows. Prove that it works and give an example on the model from (i).
(iii) What would be the time complexity for the algorithm that checks the existence of a solution?