Two companies A and B make competing versions of n different software products. Company A charges pAi for item i and company B charges pBi for its version of i. A consumer wants to buy one version of each product. While the consumer prefers cheaper versions, she also prefers to buy most software from the same company. In particular, items i and j, if bought from different companies, impose an incompatibility cost of c(i; j) on the customer. The customer's total cost of buying software is the prices paid to the two companies, plus a sum over all pairs of the respective incompatibility costs.
Design a polynomial time algorithm to determine which company the customer could buy each item from to minimize her total cost.