On-line generalized Steiner problem
Baruch Awerbuch, Yossi Azar, Yair Bartal · Symposium on Discrete Algorithms · 1996
The generalized Steiner problem (GSP) is defined as follows. We are given a graph with non-negative edge weights and a set of pairs of vertices. The algorithm has to construct minimum weight subgraph such that the two nodes of each pair are connected by a path.Off-line GSP approximation algorithms were given in Agarwal et al. (SIAM J. Comput. 24(3) (1995) 440) and Goemans and Williamson (SIAM J. Comput. 24(2) (1995) 296). We consider the on-line GSP, in which pairs of vertices arrive on-line and are needed to be connected immediately.We show that the online Min-Cost (i.e. greedy) strategy for this problem has O(log2 n) competitive ratio. The previous best algorithm was O(√nlog n) competitive (Workshop on Algorithms and Data Structures, 1993, pp. 622-633). Following this work a different (non-greedy) algorithm has been shown to achieve an O(log n) competitive ratio (Proceedings of the 29th ACM Symposium on Theory of Computing, 1997, pp. 344-353).We also consider the network connectivity leasing problem which is a generalization of the GSP. Here, edges of the graph can be either bought or leased for different costs. We provide simple randomized algorithm based on on-line generalized Steiner algorithms whose competitive ratio is within a constant factor of the best competitive algorithm for the on-line GSP.