Problem 3: Reducing algorithmic bias. (35 points) You are in charge of a team of n engineers. Your team is assigned m tasks, for some m n, that need to be completed according to the following requirements:

• Each task needs to be completed by exactly one engineer, and each engineer can complete at most one task.

• For each engineer i, you are given a set Si of all the tasks that fall within his/her area of expertise. You can assign engineer i to task j only if j e LSi.

• Each engineer is labeled as either male or female. The total number of female engineers assigned to tasks must be equal to the total number of male engineers assigned to tasks.

Design an algorithm for computing an assignment of engineers to tasks, such that all the tasks are completed, if such an assignment exists. Prove that your algorithm is correct and that it runs in polynomial time (i.e. n

Hint: Use a reduction to the Circulation with Demands and Lower Bounds problem. Recall that in the Circulation with Demands and Lower Bounds problem we are given a directed graph G = (V, E) and for each e e E we are given a capacity c(e) 0 and lower bound C(e) 2 0. We are also given for every v e V some d(v) e IR, which can be either negative, zero, or positive. The goal is to compute a circulation f, that satisfies the following conditions:

• For all e e E, C(e) f (e) c(e).

• For all G V, Ee in to v f (e) ¯ e out of v f (e) — d(v).