On-line algorithms for Steiner tree problems

The generalized Steiner tree problem is defined as follows. Given a graph with non-negative weights and a set of pairs of vertices find the minimum network of edges such that each pair of vertices is in the same connected component. We present an algorithm for the on-line Generalized Steiner Tree (GST) problem, and two other problems: Rectilinear Steiner Arborescence (RSA) and Symmetric Rectilinear Steiner Arborescence (SRSA). For each of these problems we provide polynomial time algorithms with performance ratios of O(log n). The constant factors hidden in the O-notation are small, in the case of the GST, we are within factor 2 from the proven lower bound. The previous best on-line GST algorithm (Awerbuch et at. [2]) was O(log² n) competitive.