We are starting from an $nn$ all$-$zero matrix $A.$

For every iin$\{1,$dots,$n\}$ and every $t0,$ at a cost of ${}_{i}t0$ we can increase all the entries

in the $i-$th row by $t.$

For every iin$\{1,$dots,$n\}$ and every $t0,$ at a cost of ${}_{i}t0$ we can increase all the entries

in the $i-$th colmun by $t.$

For every $i,$jin$\{1,$dots,$n\}$ and every $t0,$ at a cost of ${}_{i,j}t0$ we can increase the $ij-$entry

by $t.$

We are given ninN, the numbers ${}_{i}0,{}_{i}0,$ and ${}_{i,j}0$ for all $i,$jin$\{1,$dots,$n\}.$

Our goal is to convert $A$ to a matrix where every entry is at least $1$ at minimum total cost.

$($a$)$ Formulate this as a linear program.

$($b$)$ Write the dual of your linear program.

$($c$)$ Model this dual as a max$-$flow problem in an appropriate flow network. Conclude that the

primal problem can be modelled as a minimum cut problem in the same network.

Note that this allows us to solve the problem using a flow algorithm, which has much better

performance than general linear solvers.

$($d$)$ Show that in the optimal solution, we can select subsets $R,$Tsube$\{1,$dots,$n\}.$ For every iinR,

increase all the elements in the $i-$th row by $1$ at cost ${}_i.$ For every jinT, increase all the

elements in the column $j$ by $1$ at cost ${}_j.$ For the remaining $ij-$entries that are still zero,

increase them individually to $1$ at cost ${}_{i,j}.$