Consider the following undirected graph, taking numbers on edges as costs/weights.

(a) Apply standard Greedy Algorithm 10F to compute a maximum spanning tree of the graph.

(b) Sketch a tree like Figure 10.30 to track the new subtrees formed as edges are added to the solution, as well as the weight of the edge added to create each subtree.

(c) List the active primal constraints associated with each tree in (b).

(d) Use the structure of

(b) to determine dual variable values for those active constraints.

(e) Combine (a)–

(d) to demonstrate that your greedy solution is primal feasible in the LP relaxation of the problem, your dual solution of

(d) is dual feasible, and that together they mutually satisfy complementary slackness.

(f) Compute bound 10.69 and compare to your actual computational effort of part (a).

Transcribed Image Text:

7 1 15 20 20 2 5 10 3 1 13 11 7 4 2 3. 6 8.