ISE 632 – Final exam 2024

1. In parts  (a)  and  (b),  describe  the  solutions  and the optimal objective values to the following special cases of the minimum cost perfect bipartite matching problem on 2n vertices.

(a)  The cost matrix C satisfies cij  = ai + bj , forgiven vectors a, b ∈ Rn. (b)  The cost matrix C satisfies cij  = ai /aj , for a given (strictly positive)

vector a ∈ Rn  with unique entries (you can make use of whatever well-known inequalities might be useful here).

(c) Your friend shows you a “magic trick” involving the grid shown below:

If you select one number in each row and each column, then you will find that their sum is always equal to 85 (for example, the sum of the diagonal entries is 29+10+7+21+18). Explain why this is the case, and complete the partial grid shown below so that the sum is always equal to 113.

2.  Let G = (U ∪ V, E) be a bipartite network, with U = {u1,..., un }.

(a)  Give an algorithm for determining if there exists a matching such that, for each consecutive pair ui , ui+1, at least one of ui  and ui+1  is matched to a vertex in V.

(b)  GIve an algorithm for finding the largest possible matching such that, for each  consecutive pair  ui , ui+1,  at  most one of ui   and  ui+1   is matched to a vertex in V.

3. In a town, you have mletter carriers,n packages, and p receptacles.  Each letter carrier must travel to one package, then bring that package to a receptacle.  Obviously, each package can only be picked up by one letter carrier, and each receptacle is only capable of holding one package.  Sup- pose that the distance from carrier i to package j is cij , and the distance from package j to receptacle k is djk .

(a)  Assuming that m ≤ n and m ≤ p, give an efficient flow-based algo- rithm that assigns each carrier to a package, and then assigns that package to a receptacle, that minimizes the total distance travelled (note that if m < n then obviously some packages will not be picked up).