ISE 632 – Final exam

April 22, 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).

(b)  Show how to solve the preceding problem using only bipartite match- ing  algorithms  (any one you like).   If it  simplifies things, you are welcome to assume that m = p.

4.  Let G = (V, E) be a connected network such that |E| ≥ |V | .

(a)  Prove that it is possible to assign each vertex to an edge that touches it, such that each edge is assigned to at most one vertex.

(b)  Prove that it is possible to assign each vertex to an edge that  does not touch it, such that each edge is assigned to at most one vertex.

5.  Suppose you have a complete bipartite network G = (U ∪ V, E) such that |U| = |V |, that has a bipartite triangle inequality (i.e.  cij  ≤ cij′   + ci′j′   + ci′j  for all i,i′ , j′ , j). Describe an efficient solving the this problem.

Hint  If we had an efficient algorithm for solving the standard metric TSP

optimally, we’d have a factor 2 approximation for the problem.