assignment problem with costs

Question

i have a problem, which i'm stuck with, and cant find anywhere to start with, so i'm hopelessly turning to stackoverflow.

the problem wants us to find out if it is np-hard or polynomial, if its np-hard prove np-completeness, else give the algorithm.

the problem is as follows:

a product exists of n modules. there are two companies that can build each module, with some cost (c_ij, i: module number, j: company number). if modules a and b are built by different companies, they also have an additional cost, (p_ab). the modules a and b do not have to be successive, the same additional cost applies for a and c too. as expected, the problem wants us to find the assignment of modules to companies so that the total cost is minimum.

any ideas ?

Answer 1

It can be reduced to min cut problem, which can be found by any max flow algorithm. So what's the network? Modules will be vertecies of our graph and also we add 2 new vertices source and sink. From source we add edge to every module i with capacity Ci1. Similarly from every module i we add edge to sink with capacity Ci2. Also for any modules i and j we add edge with capacity pij (graph oriented thus there will be two edges (i j) and (j i)). It is easy to see that value of min cut is solution of the problem (modules in part of the cut with the source assign to the second company and rest modules to the first company)