You have $2$ computers denoted by $C_1$ and $C_2$ and $n$ missions $M_1,M_2, \dots M_n$. Doing the $i$-th mission on $C_1$ (resp. $C_2$) costs $a_i$ (resp. $b_i$). Moreover if you do $M_i$ and $M_j$ are done on different computers. you incur an additional cost of $d_{i,j}$. I need to find an efficient algorithm that minimizes the cost needed to do all missions.

I know how to solve this problem if all $d_{i,j}$s are $0$.

I think the solution should use either flow networks or minimal spanning trees.

Thanks in advance.


Create an undirected weighted graph $G=(V,E)$ where $V=\{C_1,C_2,M_1, \dots, M_n\}$. For each $i=1,\dots,n$ add the edge $(C_1, M_i)$ of weight $a_i$ and the edge $(C_2, M_i)$ of weight $b_i$. For each pair of distinct indices $i,j=1,\dots,n$ add the edge $(M_i, M_j)$ of weight $d_{i,j}$.

You are looking for a $C_1$-$C_2$-cut of minimum weight, namely a partition of $V$ into $A$ and $B$ such that $C_1 \in A$, $C_2 \in B$ and the weight of the edges in $E \cap (A \times B)$ is minimized.

Intuitively, $M_i \in A$ means that $M_i$ is assigned to $C_2$ and $M_i \in B$ means that $M_i$ is assigned to $C_1$. To find $(A,B)$ you can use your favorite flow algorithm to compute a maximum flow between $C_1$ and $C_2$ in $G$.

  • $\begingroup$ thank you very nuch if i can i ask flow invlolves directes graphs, how do you direct it ? $\endgroup$ Jul 15 '21 at 10:29
  • $\begingroup$ Just replace each undirected edge $\{u,v\}$ with two directed edges $(u,v)$ and $(v,u)$. Any flow that uses both directed edges can be simplified to a flow that only uses one of them (meaning that it only uses $\{u,v\}$ in one direction). $\endgroup$
    – Steven
    Jul 15 '21 at 10:32
  • $\begingroup$ thank you ! helped around 30 undergrads perpering to alg exam $\endgroup$ Jul 15 '21 at 10:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.