I have been assigned to solve a modified problem of the classic Project Allocation. 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, $J_{k}$ can be in at most $p_{k}$ evaluating groups. The group of judges that can evaluate the project of contestant $C_{j}$ is $G_{j} \subsetneq G (G_{j} \neq \varnothing) $.

Each project is evaluated by a group of n$(\le y)$ Judges, m($\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?


Your Answer

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

Browse other questions tagged or ask your own question.