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 \le 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 $S_i$ of all the tasks that fall within his/her area of expertise. You can assign engineer $i$ to task $j$ only if $j \in S_i$.
  • 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^{O(1)}$)
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 \in E$ we are given a capacity $c(e) \ge 0$ and lower bound $l(e) \ge 0$. We are also given for every $v \in V$ some $d(v) \in ℝ$, which can be either negative, zero, or positive. The goal is to compute a circulation $f$, that satisfies the following conditions:

  • For all $e \in E, l(e) \le f(e) \le c(e)$.
  • For all $v \in V, \sum_{e \text{ into } v} f(e) - \sum_{e \text{ out of } v} f (e) = d(v)$.

enter image description here

  • 4
    $\begingroup$ Please properly format your question and properly attribute all copied material. Once you have done this, please tell us what you tried and what step in particular you're having troubles with. $\endgroup$ – Steven Nov 14 at 20:40
  • 1
    $\begingroup$ Please heed How do I ask a Good Question? Claiming urgency is an excellent way to get ignored (as is "tell me the solution") - rather, edit the information Steven requested into your question. $\endgroup$ – greybeard Nov 15 at 6:57

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.