« Final exam is in the testing center 4/16 through 4/21 | Main | Avoiding premature cycles (due 3/30) »

March 25, 2005

Which edge to include/exclude? (updated, due 3/28 or 3/30)

We didn't cover all of the ideas behind this homework yet. But I would expect that you can do this on your own. Either way. Its due either monday or Wednesday. Your call.

Consider the following reduced matrix...

Changed 3/28 at 8am to have 6 rows and to actually be reduced Which edge would you include and exclude (to create to new nodes) so that you ...
Maximize the bound on the "exclude" child?
Minimize the bound on the "include" child? I changed it to minimize on 3/29. If you did maximize, that's ok, but minimize is what you really want.
 
i 9 3 0 8 3  
0 i 0 3 0 2 
5 4 i 8 3 0
9 0 3 i 5 7 
7 6 0 8 i 4
1 4 7 0 8 i
solution

Maximize the "exclude" child is the edge at row 4 column 2.
Minimize the "include" child is row row 3 column 6 or row 5 column 3. Both result in no increase to the lower bound.

Posted by jones at March 25, 2005 03:44 PM

Comments

Post a comment

Thanks for signing in, . Now you can comment. (sign out)

(If you haven't left a comment here before, you may need to be approved by the site owner before your comment will appear. Until then, it won't appear on the entry. Thanks for waiting.)


Remember me?