Let G = (V, E) be a graph with nonnegative edge weights ce for every edge e. The maximum weight matching problem is the problem of finding a matching of maximum weight. An edge-cover is a set of edges S that has the property that every vertex is the endpoint of some edge of S. The minimum weight edge-cover problem is the problem of finding an edge-cover of minimum weight.

(a)Formulate as an IP the problem of finding a maximum weight matching.

(b)Formulate as an IP the problem of finding a minimum edge-cover.

Answer rating: 100% (QA)

a Solution Maximum weighted bipartite matching is a generalization of maximum cardinality bipartite ... View the full answer