Suppose you have an algorithm A that is capable of solving the minimum

cost perfect matching problem in a complete bipartite network. Explain

how you could use this algorithm to solve the following problems:

$($b$)$ The bottleneck cost perfect matching problem in a complete bipar$-$

tite network with strictly positive edge weights, in which you seek a

perfect matching that minimizes the cost of the most expensive edge:

$minimiz{e}_{x}ma{x}_{i,j}{c}_{ij}{x}_{ij}s.t.$

${\displaystyle \underset{i=1}{\overset{n}{}}}{x}_{ij}=1$AAj

${\displaystyle \underset{j=1}{\overset{n}{}}}{x}_{ij}=1$AAi

$x_{ij}in\{0,1\}.$

You can assume that all edge weights are unique. For full marks, show

how to find the optimal bottleneck matching by calling A exactly

once. You can make the edge weights as large as you like $($like$,$ really

really big$).$