- In problem 1 in the arborescence questions, all arborescences have the same root r, where node r is part of the input.
- In problem 2. There are two natural interpretations of the greedy algorithm for greedoids. The issue is this. Suppose at some point you consider an element v (the largest weight at the moment), and do not succeed in adding v to the independent set. Do we later try to add v? In matroids, once v cannot be added to an independent set X, it also cannot be added to any set Y containing X, but this is not true for greedoids. The more interesting version of the question allows the greedy algorithm to consider the same element for addition multiple times. To be precise, here is the algorithm:Start I = emtyset
While something can be added to I
find the element x notin I such that
I+x is independent
and x has as high weight as possible
add x to I
Endwhile
I would like you to solve problem 2 for this more interesting version, though we will assign fairly large credit for the easier, less interesting version.
Select an edge e=(u,v).
Evaluate if adding (u,v) to the tour would improve it, and make the change if it improves:
- get next(v), next(w).
- if c(u,v) + c(next(v),next(w)) - c(v,next(v)) - c(w,next(w)) < 0 then reverse(next(v),w)
The goal of the problem is to invent a data structure that can maintain a tour through the nodes and do this loop for a sequence of m edges in time O(m log n) time on the average.