Who: Anupam Gupta
Where: NSH 1507
When: Noon, 2007-10-10
Stochastic Analysis of Online Steiner Tree
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.