a) In the maximum weighted perfect bipartite matching problem one is given G(V1 v_cup V2, E) and edge weights We. The goal is to find a perfect matching M with maximum weight W(M)=sum_(We)
Formulate this as a standard minimum cost flow problem. Give a directed grap G(V', A'), arc capacity Ca, arc cost Ka and supply/demand values Bv and show how to transform minimum cost to maximum weight bipartite matching
b) In the minimum weight maximum bipartite matching problem one is given G(V1 v_cup V2, E) and edge weights We. The goal is to find the minimum weight. Min W(M)= sum [over al M that are matchings of maximum cardinality]. Formulate as standard minimum cost flow.