Greedy Algorithms For The On-Line Steiner Tree And Generalized Steiner Problems
Published 1993 · Computer Science
We study the on-line Steiner tree problem on a general metric space. We show that a class of greedy on-line algorithms are O(log(d/zs))-competitive and no deterministic algorithm is better than Ω(log(d/zs))-competitive, where s is the number of regular nodes, d the maximum metric distance between any two revealed nodes and z the optimal off-line cost. Our results refine the previous known bound  and show that Algorithm SB of Bartal et al.  for the on-line File Allocation problem is O(log log N)-competitive on an N-node hypercube or butterfly network.