Two companies A and B make competing versions of n different software products.

ID: 3534827 • Letter: T

Question

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.

You can go for Shortest path Algorithms Like Floyd Warshal which run in O(V^3) time

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.