data transfer minimization problem

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.

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$$.
• 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). Jul 15 '21 at 10:32