In the online Steiner tree problem, vertices come one-by-one and have to
be connected to the root. The greedy algorithm is an O(log n) competitive
algorithm, and this is the best possible. We will obtain better guarantees
when the input sequence is not chosen by an adversary, but are just draws
from some distribution over the vertices of the graph.